This is an old revision of the document!
Table of Contents
Week 9
Chapter Scores
- Readability Score:
/ 10 
- Interest Score: / 10
Readings
Chapter 6: Dynamic Programming
6.1: Weighted Interval Scheduling
The weighted interval scheduling problem is a lot like the unweighted interval scheduling problem except that each task to be scheduled has a priority or weight to it and we want to schedule jobs such that we have the largest possible weight. With so many variables and components to consider and take into account, a greedy algorithm isn't enough. We need something that is more powerful than greedy algorithms but more efficient than brute-force algorithms.
6.2: Memoization or Iteration over Subproblems
We use recursion all the time without even thinking about it. Sometimes, however, we do more work than we have to when we come across the same call in different recursive call branches of execution. Instead of recomputing those results, we can use memoization to remember the value of previously calculated results. Every time the recursive function is called, we check the call against a memoization table. If there is no stored result for that call, we run the recursive call and store its result in the memoization table. If there is a stored result, simply return that instead of running the call again.
