Category: Readings

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

We’ll continue talking about dynamic programming.

• Here is a sample solution to part 1 of the coin-changing notes (and the original notes).
• Here is part 2 of our coin-changing notes.
• Don’t forget this week’s tutorial quiz!
• For next time, please read Section 6.3. If you are behind on the readings, Sections 6.1 and 6.2 are particularly, incredibly important. Read them!
• Our next pre-class quiz will be due on Tue and will cover sections 6.2-6.4.
• The assignment corresponding to this week’s quiz will be out soon and due next week, as usual.

We will start talking about Dynamic Programming today. We’ll kick things off with a worksheet on making change. The kind with coins, not the kind you want to see/be in the world.

• For next time, please read Section 6.2. There’s no pre-reading quiz, but students reported dynamic programming was among the harder (and more important!) topics to learn last term. Reading now will help you understand!
• Don’t forget this week’s tutorial quiz!

We’ll continue with our notes on divide-and-conquer (maybe even conquer them!) and perhaps do some live coding.

• Here again is a sample solution to the d-and-c notes.
• QuickSelect is an awesome and practical algorithm. It turns out, surprisingly, that we can also make a deterministic linear-time selection algorithm. If we get time, we may work through code for linear-time DeterministicSelect in class. (Here’s the Jupyter Notebook for that code.)
• Before class next time, read Section 6.1 and complete the pre-reading quiz due Tue at 10PM.
• There is a tutorial quiz this week (the week after mid-term break).
• Don’t forget to read sections 5.3 and 5.4 plus the Master Theorem entry on Wikipedia. They’re not on the pre-class quiz, but they are tremendously important (and easy for us to assess!).