Some notes from a class from many years ago:
There are three factors that matter for any algorithm:
1. Focus on the recursive step. Once you have that, you’re 90% done. In other words, how do I break it up into smaller problems?
2. What values will you store and update as the algorithm runs? Example: if min < curr, min = curr
3. In what order will you look at your input? (example: binary search)
For a greedy algorithm (example: given a set of intervals, find the biggest subset of non-overlapping intervals):
- Identify a part or subset of the optimum — something that has to exist in the optimum solution (pick the interval that ends first).
- Reduce problem size (throw out overlapping intervals) [sometimes an “exchange trick” helps for this].