- Brute Force
- Divide and Conquer
- Dynamic Programming
Divide and Conquer
Recipe for Divide and Conquer Algorithms
- Divide the input into smaller sub problems
- Conquer the sub problems recursively
- Combine the solutions of the sub problems into a final solution
Recipe for Greedy Algorithms
- Construct a solution iteratively, via a sequence of myopic decisions, and hope that everything works out in the end
Features of Greedy Algorithms
- Easy to come up with one or more greedy algorithms
- Easy to analyse the running time
- Hard to establish correctness
- Most greedy algorithms are not always correct, use with caution
Dynamic programming was pioneered in the 1950s by Richard E. Bellman of the RAND corporation.
Recipe for Dynamic Programming
- Identify a relativity small collection of sub problems
- Show how to quickly and correctly solve “larger” sub problems given the solutions to “smaller” sub problems
- Show how to quickly and correctly infer the final solutions from the solutions to all of the sub problems.
Dynamic Programming algorithm runtime
- $f(n)$ = number of sub problems
- $g(n)$ = time per sub problem (including combining previous solutions)
- $h(n)$ = post processing (inferring final solution)
Difference between Divide and Conquer and Dynamic Programming
- Divide and conquer commits to a single way of dividing input into smaller sub problems. Dynamic programming considers multiple ways.
- Divide and conquer sub problems are typically unique while Dynamic programming sub problems can often benefit from memoization.
- Divide and conquer typically speeds up a polynomial-time algorithm. Dynamic programming takes exponential (e.g. $O(k^n)$) run time algorithms and reduces them to polynomial time (e.g. $O(n^2)$).
- Divide and conquer identifies sub problems in order to optimize a run time. Dynamic programming identifies sub problems with an emphasis on correctness.
- Divide and conquer algorithms typically recurse on sub problems of half the size. Dynamic programming will recurse on only slightly smaller sub problems.
- Divide and conquer is a special case of Dynamic programming.