We’ll do some combination of live-coding of dynamic programming and starting in on our “what’s in a reduction” handout. (A problem by any other name would be as complete??) This is the start to our discussion on NP-completeness.
- For next time, please read Section 8.2 and skim Section 8.10. Keep skimming 8.10 as we read each section. It will help to keep the problems straight in your head! (Note that we won’t discuss every type of problem categorized in 8.10, however.)
- The reading quiz for next time is on 8.1 (the reading for last time).
- We’ll have a reading quiz due Sunday on 8.2 and 8.3. (So, get an early start on the reading if you’d like!)
- As usual for this week’s quiz, we’ll post the quizzes each day with the full assignment on Friday.