Today we move on to memoization and dynamic programming! This is a widely applicable technique that also lets us practice algorithm design and analysis, designing recursive solutions, and designing iterative solutions. Woo-hoo! 🙂

- Here are today’s notes (part 1 on Memoization and DP using the change example).
- For Monday,
**read Section 6.1**.
- I
**will** try to post a quiz, but the UBC Survey system is crashing for me. If I cannot post it by noon on Saturday, I won’t, but **please** work the problems anyway!
Here is the quiz:

- The recursive solution to the weighted interval scheduling problem has to make one key decision among two or more choices by
**trying all the choices** and picking the best. What is the decision?
- Which among all the previous events will go before this event
- Whether or not to include this event in the solution
- Whether the next event’s start time is before this event’s finish time (i.e., they conflict)

- How do we figure out that there are only n+1 total possible sub-problems in the memoized solution?
- Because the only legal arguments to the algorithm are 0 through n.
- Because of the algorithm’s “for” loop going from 0 up to n.
- Because the algorithm runs in O(n) time.

- We’re working on grading the exam and will be done soon. However, scanning/handback is likely to take until roughly class time on Wednesday.
- There will be no quiz in next week’s class. Sorry! Too busy with exam prep/marking to get one together 🙁