1 of 55

CSE 421 Section 5

Dynamic Programming

2 of 55

Administrivia

3 of 55

Announcements & Reminders

Midterm Exam: Monday Nov 3 in ECE 105 @ 5.30pm-7:30pm (actual exam time: 100 minutes)

If you have a situation that prevents you from making it, let Andrea know and we will�schedule another exam.

4 of 55

Writing a Dynamic Programming Algo

5 of 55

Dynamic Programming

Take recursive ideas from divide and conquer, but speed up finding the solution by optimizing the work by reordering and saving the results so we don’t have to repeat anything!�
Key idea:

use English words to explain the output of the recursive function
write a recurrence for the output of the recursive function

Memoization: save results of intermediate calculations so we don’t need to repeat

6 of 55

The Strategy (SLIGHTLY DIFFERENT FOR DP)

Read and Understand the Problem
Generate Examples
Write the Dynamic Program
Analyze the Dynamic Program

7 of 55

Dynamic Programming Process (from lecture)

This is what we’ll do in parts 3 and 4 of our strategy:

Define the object you’re looking for.
Write a recurrence to say how to find it.
Design a memoization structure.
Write an iterative algorithm.

8 of 55

Problem 1 – Lots of fun, with a normal sleep schedule

9 of 55

1. Read and Understand the Problem

10 of 55

Problem 1.1 – Fun & Sleep

Are there any technical terms, or words that seem technical? ��
What is the input type? (Array? Graph? Integer? Something else?) ��
What is your return type? (Integer? List?)

11 of 55

Problem 1.1 – Fun & Sleep

Are there any technical terms, or words that seem technical? ��
What is the input type? (Array? Graph? Integer? Something else?) ��
What is your return type? (Integer? List?)

12 of 55

Problem 1.1 – Fun & Sleep

Are there any technical terms, or words that seem technical? ��
What is the input type? (Array? Graph? Integer? Something else?) ��
What is your return type? (Integer? List?)

“consecutive” means in a row

“maximize the sum of the happinesses” is semi-technical?

13 of 55

Problem 1.1 – Fun & Sleep

Are there any technical terms, or words that seem technical? ��
What is the input type? (Array? Graph? Integer? Something else?) ��
What is your return type? (Integer? List?)

“consecutive” means in a row

“maximize the sum of the happinesses” is semi-technical?

int[]

14 of 55

Problem 1.1 – Fun & Sleep

Are there any technical terms, or words that seem technical? ��
What is the input type? (Array? Graph? Integer? Something else?) ��
What is your return type? (Integer? List?)

int[]

int (the maximum sum of happinesses)

“consecutive” means in a row

“maximize the sum of the happinesses” is semi-technical?

15 of 55

2. Generate Examples

16 of 55

Good Examples Help!

You should generate two or three sample instances and the correct associated outputs. �
It’s a good idea to have some “abnormal” examples – consecutive negative numbers, very large negative numbers, only positive numbers, etc.�
Note: You should not think of these examples as debugging examples – null or the empty list is not a good example for this step. You can worry about edge cases at the end, once you have the main algorithm idea. You should be focused on the “typical” (not edge) case.

17 of 55

Problem 1.2 – Fun & Sleep

Generate two examples with their associated outputs. Put some effort into these! The more different from each other they are, the more likely you are to catch mistakes later.

Work through generating some examples, and then we’ll go over it together!

18 of 55

Problem 1.2 – Fun & Sleep

Generate two examples with their associated outputs. Put some effort into these! The more different from each other they are, the more likely you are to catch mistakes later.

19 of 55

Problem 1.2 – Fun & Sleep

Generate two examples with their associated outputs. Put some effort into these! The more different from each other they are, the more likely you are to catch mistakes later.

20 of 55

3. Write the Dynamic Program

21 of 55

Problem 1.3 – Fun & Sleep

Formulate the problem recursively – what are you looking for (in English!!), and what parameters will you need as you’re doing the calculation?�
Write a recurrence for solving the problem you defined in the last part (the recurrence is for the answer, not the running time). �
What is your final answer (e.g. what parameters for the recurrence do you need? Is it a single value or the max/min of a set of values?)? �
Give a brief justification for why your recurrence is correct. You do not need a formal inductive proof, but your intuition will likely resemble one.

Start brainstorming some answers to these questions.

22 of 55

Problem 1.3 – Fun & Sleep

Formulate the problem recursively – what are you looking for (in English!!), and what parameters will you need as you’re doing the calculation?
Write a recurrence for solving the problem you defined in the last part (the recurrence is for the answer, not the running time).

First, let’s take some time to brainstorm about what the recurrence could be. What is our OPT finding? How many parameters do we need to calculate it? What are those parameters for?

23 of 55

Problem 1.3 – Fun & Sleep

Formulate the problem recursively – what are you looking for (in English!!), and what parameters will you need as you’re doing the calculation?

24 of 55

Problem 1.3 – Fun & Sleep

Formulate the problem recursively – what are you looking for (in English!!), and what parameters will you need as you’re doing the calculation?

25 of 55

Problem 1.3 – Fun & Sleep

Write a recurrence for solving the problem you defined in the last part (the recurrence is for the answer, not the running time).

26 of 55

Problem 1.3 – Fun & Sleep

Write a recurrence for solving the problem you defined in the last part (the recurrence is for the answer, not the running time).

27 of 55

Problem 1.3 – Fun & Sleep

What is your final answer (e.g. what parameters for the recurrence do you need? Is it a single value or the max/min of a set of values?)?

28 of 55

Problem 1.3 – Fun & Sleep

What is your final answer (e.g. what parameters for the recurrence do you need? Is it a single value or the max/min of a set of values?)?

29 of 55

Problem 1.3 – Fun & Sleep

Give a brief justification for why your recurrence is correct. You do not need a formal inductive proof, but your intuition will likely resemble one.

30 of 55

Problem 1.3 – Fun & Sleep

Give a brief justification for why your recurrence is correct. You do not need a formal inductive proof, but your intuition will likely resemble one.

31 of 55

4. Analyze the Dynamic Program

32 of 55

Problem 1.4 – Fun & Sleep

Describe a memoization structure for your algorithm.��
Describe a filling order for your memoization structure.��
State and justify the running time of an iterative solution.

Start brainstorming some answers to these questions.

33 of 55

Problem 1.4 – Fun & Sleep

Describe a memoization structure for your algorithm.��
Describe a filling order for your memoization structure.��
State and justify the running time of an iterative solution.

34 of 55

Problem 1.4 – Fun & Sleep

Describe a memoization structure for your algorithm.��
Describe a filling order for your memoization structure.��
State and justify the running time of an iterative solution.

35 of 55

Problem 1.4 – Fun & Sleep

Describe a memoization structure for your algorithm.��
Describe a filling order for your memoization structure.��
State and justify the running time of an iterative solution.

36 of 55

Problem 1.4 – Fun & Sleep

Describe a memoization structure for your algorithm.��
Describe a filling order for your memoization structure.��
State and justify the running time of an iterative solution.

37 of 55

Problem 2: �Longest Increasing Subsequence

38 of 55

Problem 2 – Longest Increasing Subsequence

Given an array A, find the longest sub-array of A whose elements are in increasing order.

As an example, [10, −2, 5, 0, 3, 11, 8] has a longest increasing subsequence of 4 elements: [−2, 0, 3, 8]

39 of 55