Here is the assignment version of the Mon 3PM quiz question.

# Month: October 2016

## Lecture 2016/10/31

**Boo!**

Today we’ll work on dynamic programming in two dimensions.

- Here are the new DP in 2-D notes for today.
- For next lecture, please read section 6.5 in the textbook. (No reading quiz for Wed, however.)
- Tue/Wed tutorial students: remember the quiz this week!
- Everyone: get started on the so-far-released quiz/assignment questions.

## Assignment/Quiz 4, Mon 9AM Edition

Here is the assignment version of the Mon 9AM quiz question.

## Lecture 2016/10/28

Today we’ll continue with (and probably finish) our work on the change-making memoization/dynamic programming problem.

- Here are sample solutions for part 1 and part 2 (updated with corrections by Victoria and others; thanks!) of the notes.
- For Monday, 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).
- Don’t forget to expect quizzes in next week’s tutorial.

## Lecture 2016/10/26

We’ll continue to part 2 of memoization and dynamic programming.

- Here are the part 2 notes.
- For Friday, please read section 6.3 of the textbook, but there is no pre-class quiz. (
**PLEASE**finish 6.1 and 6.2 at minimum ASAP, however, or class time will be far less useful than it should be!) - Loads of midterm exam info has been posted on Piazza.
- Expect a tutorial quiz next week!

## Lecture 2016/10/24

Today we continue working on memoization and dynamic programming.

- For Wednesday,
**read Section 6.2**. - Midterm exams are graded and in the process of being scanned. More info soon!

## Protected: Midterm Sample Solution

## Blank copy of our Midterm Exam

Here is a blank copy of our midterm exam. (The same as the midterm, but without the cover page/exam rules and instead with a licensing footer attached.)

## Lecture 2016/10/21

Today we move on to memoization and dynamic programming! This is a widely applicable technique that also lets us practice algorithm design and analysis, designing recursive solutions, and designing iterative solutions. Woo-hoo! 🙂

- Here are today’s notes (part 1 on Memoization and DP using the change example).
- For Monday,
**read Section 6.1**. - I
**will**try to post a quiz, but the UBC Survey system is crashing for me. If I cannot post it by noon on Saturday, I won’t, but**please**work the problems anyway!Here is the quiz:

- The recursive solution to the weighted interval scheduling problem has to make one key decision among two or more choices by
**trying all the choices**and picking the best. What is the decision?- Which among all the previous events will go before this event
- Whether or not to include this event in the solution
- Whether the next event’s start time is before this event’s finish time (i.e., they conflict)

- How do we figure out that there are only n+1 total possible sub-problems in the memoized solution?
- Because the only legal arguments to the algorithm are 0 through n.
- Because of the algorithm’s “for” loop going from 0 up to n.
- Because the algorithm runs in O(n) time.

- The recursive solution to the weighted interval scheduling problem has to make one key decision among two or more choices by
- We’re working on grading the exam and will be done soon. However, scanning/handback is likely to take until roughly class time on Wednesday.
- There will be no quiz in next week’s class. Sorry! Too busy with exam prep/marking to get one together 🙁

## Solution to Tug-O-War Notes

Here’s a solution to the tug-o-war notes (quicksort/quickselect).