CPSC 320

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!).