CPSC 320 2019S2

Today we will continue working on a 2D dynamic programming algorithm to compute the longest common substring of two strings. If we have time, we may start talking about NP-completeness.

Announcements for today:

• Assignment #4 is due tomorrow at 11 PM.

Here are today’s clicker questions.

Today we’ll start on our memoization/dynamic programming unit with a worksheet on making change (the kind with coins, not the kind you wish to be/see in the world).

Announcements for today:

• The midterm exam is on Wednesday. We will discuss logistics at the beginning of class today. If you miss the beginning of today’s class, make sure you read the exam information we have on Piazza.

Today we’ll finish up our worksheet on divide and conquer and talk about a cool variant of the QuickSelect algorithm with better theoretical performance guarantees. We also have a handout on the Master Theorem.

Announcements for today:

• Assignment 3 is up on the course webpage. This one is just practice for the midterm exam and won’t be for submission. We’ll release solutions on Sunday morning.
• Tutorials today will be about proofs on 320 exams. The proof questions we ask on exams tend to be structured a bit differently from the ones we ask on assignments (though they obviously deal with the same kinds of concepts). Tutorials today will work through some examples.
• Your first reading quiz on dynamic programming is due on Sunday night.

Here are today’s clicker questions, along with PDF versions of today’s Jupyter notebooks on how to select the pivot, and Steve Wolfman’s more elaborate and complete notebook on the actual algorithm. UBC Blogs does not allow upload of .ipynb files, so the actual notebooks can be downloaded on Piazza.