Month: March 2017

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.

 

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.

There’s still more to do with dynamic programming. The recurrence relation we used to describe the number of coins needed to make n cents of change had just one parameter (and so a one-dimensional table/array), but our recurrence relations/recursive functions can have more parameters.

Memoization/DP can still work. We may need a table with more dimensions. In fact, we can in general use a hash table where the key is a tuple of the parameter values.

Off we go to the Longest Common Subsequence, then!

• Here are the new DP in 2-D notes for today.
• For next class, please read section 6.5 in the textbook. (No reading quiz, however.)
• Keep going on the assignment due Friday!
• Also, here’s auto-memoizing code in Racket (actually using CPSC 311’s PLAI language variant, but other than the testing framework, most of it should transfer to plain Racket) and a built-in auto-memoizing decorator in Python.

We’ll continue taking our wildly inefficient “brute force” algorithm for making change and turning it into a memoized and then dynamic programming solution.

• Here are sample solutions for part 1 and part 2.
• For next class, please read Section 6.4 of Chapter 6. There will be a pre-class quiz (for which invitations have been sent by mail, as usual).
• Assignment #4 is posted on the blog and due on Friday!
• Note that Steve will miss the latter part of this week; there’s a post pinned to the top on Piazza describing what will happen to his Thu/Fri office hours