Here is the full version of Assignment #5. Dive in, have fun! 🙂
In case it helps, here is the LaTeX source for A#5.
Handouts and Notes for 2017/03/17
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!
Thursday 11AM Quiz Question
Here is the Thursday 11AM Quiz 5 Question. NOTE: the comment about “IsPow2” is meant for the Wednesday quiz question instead. That’s corrected in tomorrow’s full assignment release.
Wednesday 1PM Quiz Question
Here is the Wednesday 1PM Quiz 5 Question. NOTE: the bound on j should be “< i” rather than less-than-or-equal. That’s corrected on Friday’s full assignment release. You should also feel free to assume you have a function IsPow2(x) that determines whether an integer is a power of 2. (Otherwise, you could use logs and rounding or assumptions about reasonable binary representations if you like.)
Quiz 5 Pre-Release Readings
Here are the pre-readings for Quiz 5. Note that Tue, Wed, and Thu tutorials will use the “pre-reading” for section 1 (i.e., no pre-reading). All Friday problems will use one of the other pre-readings.
As always, be sure you look through this before your tutorial!
Handouts and Notes for 2017/03/15
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.
Tuesday 1PM Quiz Question
Here is the Tuesday 1PM Quiz 5 Question.
Handouts and Notes for 2017/03/13
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!
Handouts and Notes for 2017/03/13
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.
Handouts and Notes for 2017/03/10
We’ll continue working on the LCS problem!
- For next class, read Section 6.6 and complete the pre-class quiz due Sunday.
- Here are the LCS notes and a sample solution.
- Assignment #4 is due on Fri 10 Mar!
- As usual, expect another tutorial quiz next week.