Discussion Assignment #1
In your own words describe both brute force algorithms and branch and bound algorithms and identify the differences between the two. As part of your description you must discuss the Asymptotic behavior of each and discuss why this is important and how this might factor into the decision to use either algorithm design.
Answer
A brute force algorithm simply aims to try all possible solution to the problem and it stops only when it finds the valid solution. It is easy to built an algorithm like this, but it is not always efficient especially with large inputs.
Hackers use this strategy to enter a password to have an illegal access, by trying all possible passwords. For example, if a hacker want to try all possible passwords, then the time complexity would be O(m*n) where m is the number of allowed characters in the password and n is the maximum length of the password. Luckily, this would take many tries in most of the modern secured systems!
On the other hand, according to Gao (2014), branch and bound algorithms work iteratively to find the most optimal solutions in a careful manner, and therefore this kind of algorithms fits well with optimization problems.
This kind of problems can be solved by finding the valid solutions, comparing them, and pick the optimal one, knowing that a structure called state space tree is generated to search for find the optimal solution. Branch and bound strategy solve these problems efficiently by omitting the unfruitful solutions during the branching (or searching) because processing such is a time wasting process. Of course, the elimination of unfruitful solutions is done based on the previously evaluated solutions that cost less (i.e. more optimal).
In the end, each type of the former algorithms fits with specific kinds of problems. For optimization problems, I would definitely go with branch and bound strategy, since it is more computationally efficient. As for brute-force strategy, in my opinion it can be used to design a basic solution for a medium-difficulty searching and sorting problems. If it works well with the size of input, then it is fine! Otherwise, we can find out how it can be optimized either by using divide and conquer strategy or another technique.
Discussion Assignment #2
The following table provided by Shewchuk (2006) is useful to analyze the following function asymptotically and knowing which term grows faster.
Function | Common Name |
Constant | |
Logarithmic | |
Log-squared | |
Root-n | |
Linear | |
n log n | |
Quadratic | |
Cubic | |
Quartic | |
Exponential | |
Exponential | |
Factorial | |
ㅤ |
Exercise 1
because the exponential term grow faster than
because the exponential term grow faster than
because the term grow faster than
Exercise 2
For the following Θ complexities write down a tight and a non-tight O bound, and a tight and non-tight Ω bound of your choice, providing they exist.
Θ( 1 )
Θ( √n )
Θ( n )
Θ( n2 )
Θ( n3 )
For your discussion post, explain in your own words how you solved the exercise. Include one or two examples to explain your thought process to show what is occurring and how the methodology works. Demonstrate your understanding of how to solve each exercise. Use APA citations and references for any sources used.
Reference
Gao, J. (2014). Branch and bound (BB). Northwestern University Open Text Book on Process Optimization. https://optimization.mccormick.northwestern.edu/index.php/Branch_and_bound_(BB)
Shewchuk, J. (2006). CS61B: Lecture 19 Asymptotic Analysis. University of California, Berkeley. https://www.youtube.com/watch?v=X8Ba--V4sGA