Chapter 6

We have previously discussed Interval Scheduling with all weights equal to 1, but this section delves into a more general case of the problem where values can vary. Unfortunately, the greedy algorithm we previously discussed in the unweighted case will no longer be optimal for what we are doing. Thus, we need a new algorithm. In fact, we must move away from greedy algorithms all together, as one may have guessed, we now must use dynamic programming. What we ultimately use involves recursion and memoization. Using memoization allows us to save values after calculating them once so that they may be referred to easily in the future without having to recalculate them over and over again. This is especially useful with all of the recursive calls to help lower our runtime complexity. Without memoization, the algorithm would run in exponential time. After introducing the memoization, the runtime goes down from exponential all of the way to O(n), which is obviously a tremendous improvement. This goes to show the power of memoization in the right situation.

This section was relatively interesting as dynamic programming is something I saw in Theory of Computation that I really did not understand at the time, probably due to the difficulty of the problem is used on. Everything in this section, however, makes perfect sense. Overall, I give it a 6/10.