CPSC 320

Today we’ll continue to talk about NP-completeness and reductions.

• Please read section 8.4 for next class (but the next pre-class quiz will be due before the following class).
• Here is a sample solution to our “What’s In a Reduction” handout.
• We may get a chance to start part 1 of our handout on laying pipe.
• Don’t forget the assignment due Friday!

Today we’ll continue to talk about NP-completeness and reductions.

• For next class, please read section 8.3 and complete the pre-class quiz on 8.2 and 8.3.
• Here’s a sample solution to our current notes on reductions and NP-completeness.
• Here is code implementing memoized and DP versions of Longest Common Subsequence. Here’s a Jupyter Notebook version and plain Python version. (I use the CPSC 103 test library, but it should be pretty easy to remove that dependency!)
• Start in on the assignment, due next week and posted at the end of the day Friday!

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.

Sorry to be late on this! No new handouts/notes for today. We’re continuing DP in 2-D.

• For next class, please read Section 8.1 and the Chapter 8 intro and complete the associated reading quiz (which is due on Thu rather than Tue, since I took a while getting this posted!).(Note: this is a long-ish section; so, it’s good that you have a bit of extra time to finish the quiz. I hope you’ll find that, since we’ve already discussed reductions many times, this will be a new twist on how to use them but not brand new material. Take time over the next week or so to consolidate your understanding of this very important section!)
• Don’t forget there will be tutorial quizzes this week!

Today we’ll probably finish off the LCS problem!

• Here again are the LCS notes and a sample solution.
• For next class, please read section 6.8. (This is the last required section in the dynamic programming chapter, although we recommend the other sections as interesting reading, particularly if you’re continuing on to CPSC 445, which uses DP heavily). No reading quiz.
• Don’t forget there will be tutorial quizzes this week! As usual, we will release assignment versions daily, with the full assignment released at the end of Friday.