Algorithm Design Notes

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].
- Recurse.