## July 29 Handouts and Notes

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.

## Quiz 4 and (partial) sample solution

To help you with question 4 of the assignment, here is the individual version of quiz 4 and a partial sample solution.

## July 26 Handout and Notes

In today’s class we’ll work on making our change-making algorithm more efficient using memoization. If we have time, we may also start on a 2D dynamic programming algorithm to compute the longest common substring of two strings.

Announcements for today:

• Our final exam has been scheduled for 12:00-2:30 pm on Tuesday August 13.
• Assignment 4 has been released and is due on Tuesday.
• Your tutorial quiz is today. It’s based on question 4 of your assignment and will provide a hint to help you with that question.

Here are today’s clicker questions.

## Assignment #4

Here is Assignment #4, due 11 pm on July 30. LaTeX source for the assignment will be posted on Piazza (because UBC blogs doesn’t allow upload of .tex files).

## July 22 Handouts and Notes

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.

## July 19 Handouts and Notes

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.

## Assignment #3 (for practice only)

Here is a link to Assignment #3. It is not for submission and will not be graded. Its purpose is to give you practice with greedy algorithms before the midterm exam.

Solutions will be released on Sunday, July 21 (but we recommend you work through every problem before you look at the solutions!).