1 of 53

Lecture 19: Dynamic Programming

CSE 373: Data Structures and Algorithms

1

2 of 53

Administrivia

  • Exercise 5 due today, Exercise 6 out now!!!
    • last exercise of the quarter!!!!!???
  • Exercise 4 grades not released today, pushed to sunday
    • higher volume of extensions on this exercise
  • extensions
    • just ask….don’t feel bad!
  • P4 and exercise 6 are the only assignments left in the class….

​

  • EC meme competition…
  • i lied…

3 of 53

Dynamic Programming

3

4 of 53

What is Dynamic Programming

An algorithmic technique of optimizing a given algorithm by:

  • identifying the final solution as a summation of solutions to smaller sub problems
    • Building off of “divide and conquer”
  • Intelligently ordering our solutions to the sub-problems to build up to the final solution

4

5 of 53

Dynamic Programming Techniques

  1. Design “brute force” recursive solution
  2. Take a recursive algorithm and find the overlapping subproblems, then cache the results for future recursive calls. (Memoize)
    1. Store subproblems of the main problem so we don’t have to re-compute them when we need them later on in solving the main problem
  3. Bottom up approach

​

A little confusing? Don’t worry, you are not alone!

5

6 of 53

Question

Given a number n, print n-th Fibonacci Number.

​

How can we solve this problem in the most optimized way?

6

7 of 53

Clarify

  1. Can n be a non-positive number?
    1. Depends, n can be 0, but not negative.
  2. Can we use additional data structures?
    • Yes, assume we want the fastest overall runtime.
  3. What should be the result when n = 0?
    • The result should be 0, before the first 1 in the sequence 1, 1, 2, …,Fib(n)

7

8 of 53

Example

Edge Case 1:

n = 0; Fib = None

Output = 0

Edge Case 2:

n = 1; Fib = 1

Output = 1

Middle Case 1:

n = 2; Fib = 1, 1

Output = 1

Middle Case 2:

n = 9; Fib = 1, 1, 2, 3, 5, 8,

13, 21, 34

Output = 34

8

9 of 53

Approach

Brute Force:

  1. Use a recursive function to solve
  2. Starting with n and descending down, recursively return the addition of the last and second last numbers of our sequence
  3. End our recursion when we hit our base case n = 1

Has O(2^n) runtime with O(n) space complexity…

There is a faster way using Dynamic Programming…

9

10 of 53

Recursive Solution

public static int fib(int n) {

if (n <= 1) {

return n;

}

return fib(n-1) + fib(n-2);

}

10

11 of 53

Memoized Dynamic Programming Solution

public int fib(int n, int[] memo) {

if (memo[n] != null) {

return memo[n];

} else if (n <= 1) {

return n;

} else {

int result = fib(n-1, memo)

+ fib(n-2, memo);

memo[n] = result;

return result;

}

}

11

Detailed walkthrough of this solution

2n+1 recursive calls gives us O(n) instead of O(2n)

12 of 53

Fibonacci Memoized Solution Expression

Memo[i] = { 0 , if i = 0 }

{ 1 , if i = 1 }

{ Memo[1] + Memo[2] , otherwise }

​

Fib(i) = { Memo[0] , if i = 0 }

{ Memo[1] , if i =1 }

{ Memo[i-1] + Memo[i-2] , otherwise }

​

​

This might be on the Final Exam….

12

13 of 53

Bottom Up Dynamic Programming Solution

public int fib(int n) {

int f[] = new int[n+1];

f[0] = 0;

f[1] = 1;

f[2] = 1;

for (int i = 3; i <= n; i++) {

f[i] = f[i-1] + f[i-2];

}

return f[n];

}

13

Detailed walkthrough of this solution

14 of 53

Optimize

  • Optimized: Use Dynamic Programming to pre-compute Fib sequence up until n and return. Runs in O(N) runtime.
  • Optimized no additional data structure: We compute the value of our current term with a fixed number of elements. O(1)
  • Note: When you are computing a value in a sequence in an interview, think about using DP if applicable.

14

15 of 53

Implement

  • Create 3 variables to hold our second last value, our last value, and our current value with respect to our current term in the sequence when iterating.
  • Iterate in a for-loop until we hit term n and add our last and second last values and set them equal to our current value.
  • When we exit the for-loop, we will have computed the Fibonacci value at n.

15

16 of 53

Implement - Java Code

static int fib(int n) {

int a = 0, b = 1, c;

if (n == 0)

return a;

for (int i = 2; i <= n; i++) {

c = a + b;

a = b;

b = c;

}

return b;

}

16

17 of 53

Test

Test with Middle Case 2:

n = 9

Fib = 1, 1, 2, 3, 5, 8, 13, 21, 34

​

Resulting variable values after for loop ends:

a = 21, b = 34, c = 34

Return b = 34

​

17

18 of 53

Question - Practice on your own! :))

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

​

How can we solve this problem in the most optimized way?

18

19 of 53

Clarify

  1. Can n be a non-positive number?
    1. No, n must be equal to or greater than 1.
  2. Can we use additional data structures?
    • Yes, assume we want the fastest overall runtime.
  3. Can we climb the same number of steps in a row?
    • Yes, you can climb in any combination of 1 or 2 steps.

19

20 of 53

Example

Edge Case 1:

n = 1; 1. Take one step forward.

Output = 1

​

Edge Case 2:

n = 2; 1) 1 + 1 step 2) 2 steps

Output = 2

Middle Case:

n = 3;

1) 1 + 1 + 1 steps

2) 1 + 2 steps

3) 2 + 1 steps

Output = 3

20

21 of 53

Approach

Brute Force:

  1. Use a recursive function to solve
  2. Starting with n and descending down, recursively return the sum of the combinations it took to get to the last and second last steps from our current step
  3. End our recursion when we hit our base cases n = 1, n = 0

Has O(2n) runtime with O(n) space complexity…unless…dynamic programming…

21

22 of 53

Optimize

  • Optimized: Use Dynamic Programming to pre-compute the combinations of steps it takes to get to n and return. Runs in O(N) runtime.
  • Optimized no additional data structure: We compute the value of our current step with a fixed number of elements (our last and second last step it took to get to our current step). O(1)
  • Note: We are computing a value in a sequence, just like the Fibonacci problem…

22

23 of 53

Implement

  • Create 3 variables to hold the number of combinations it took to get to our second last step, our last step, and our current step with respect to our current step in the sequence when iterating.
  • Iterate in a for-loop until we hit term n and add our last and second last steps’ combinations and set them equal to the number of combinations to get to our current step.
  • When we exit the for-loop, we will have the number of combinations to get to step n.

23

24 of 53

Implement - Java Code

public int climbStairs(int n) {

int secondLast = 1, last = 1, current = 1;

if (n == 1)

return last;

for (int i = 2; i <= n; i++) {

current = secondLast + last;

secondLast = last;

last = current;

}

return last;

}

24

25 of 53

Fun Fact

The previous solution runs faster than 100% of leetcode solutions for the problem…which is the first time I have ever gotten a 100%...if you haven’t been convinced of the power of DP yet…you should be now…

26 of 53

Test

Test with Middle Case:

n = 3

3 different ways to get to step 3

​

Resulting variable values after for loop ends:

secondLast = 2, last = 3, current = 3

Return last = 3

​

26

27 of 53

More Examples of Dynamic Programming Problems

  • Count the different ways to move through a 6x9 grid
  • Given a set of coins, how can we make 27 cents using the smallest number of coins?
  • Given a set of strings, what are the possible ways to construct the string “potentpot”
  • Knapsack problem

Helpful walk through videos:

5 Simple Steps for Solving Dynamic Programming Problems

27

28 of 53

P4 Dynamic Programming Portion

Watch Intro Video Here

  • (Thank you to Past TA Sherdil for making a long time ago….)

TAs not allowed to help you code Extra Credit Dynamic Programming Part of P4

  • high level non-specific DP questions only, not related to P4

28

29 of 53

Embedded Video From Previous Slide

29

30 of 53

Questions?

30

31 of 53

31

32 of 53

32

33 of 53

  1. Use a DAG to visualize which box can stack on top of which

33

34 of 53

2. Identify sub problems: Paths in the DAG represent valid stacks

34

35 of 53

3. Find how subproblems build to larger solution

35

36 of 53

4. Generalize relationship between subproblems and final solution

36

37 of 53

5. Implement solving subproblems in correct order

37

38 of 53

38

39 of 53

Divide and Conquer

  • There’s more than one way to divide!
  • Mergesort:
    • Split into two arrays.
    • Elements that just happened to be on the left and that happened to be on the right.

​

  • Quicksort:
    • Split into two arrays.
    • Roughly, elements that are “small” and elements that are “large”
    • How to define “small” and “large”? Choose a “pivot” value in the array that will partition the two arrays!

40 of 53

Quick Sort (v1)

0

8

0

1

2

3

4

5

6

7

8

2

91

22

55

1

7

6

Divide

0

1

2

3

2

1

7

6

0

1

2

91

22

55

0

1

2

3

1

2

6

7

0

1

2

3

4

5

6

7

1

2

6

7

8

22

55

91

Combine

0

1

0

2

0

6

0

7

0

8

0

22

0

1

2

3

1

6

7

55

0

55

0

91

…

…

Conquer

Choose a “pivot” element, partition array relative to it!

Again, no extra conquer step needed!

Simply concatenate the now-sorted arrays!

PIVOT

0

8

https://www.youtube.com/watch?v=ywWBy6J5gz8

41 of 53

Quick Sort (v1): Divide Step

0

8

0

1

2

3

4

5

6

7

8

2

91

22

55

1

7

6

Divide

0

1

2

3

2

1

7

6

0

1

2

91

22

55

Recursive Case:

  • Choose a “pivot” element
  • Partition: linear scan through array, add smaller elements to one array and larger elements to another
  • Recursively partition

PIVOT

Base Case:

  • When array hits size 1, stop dividing.

0

1

7

6

0

1

0

2

PIVOT

PIVOT

0

1

22

55

0

91

PIVOT

PIVOT

0

6

0

7

0

22

0

55

42 of 53

Quick Sort (v1): Combine Step

0

8

Combine

Simply concatenate the arrays that were created earlier! Partition step already left them in order ☺

0

1

0

2

0

91

0

6

0

7

0

22

0

55

0

1

6

7

0

1

22

55

0

1

2

3

4

5

6

7

1

2

6

7

8

22

55

91

0

1

2

3

1

2

6

7

0

1

2

22

55

91

43 of 53

Quick Sort (v1)

quickSort(list) {

if (list.length == 1):

return list

else:

pivot = choosePivot(list)

smallerHalf = quickSort(getSmaller(pivot, list))

largerHalf = quickSort(getBigger(pivot, list))

return smallerHalf + pivot + largerHalf

}

Worst case runtime?

​

​

Best case runtime?

​

In-practice runtime?

​

Stable?

​

In-place?

No

Can be done!

 

0

1

2

3

2

1

7

6

0

1

7

6

0

1

0

2

PIVOT

PIVOT

0

6

0

7

 

 

0

1

2

3

1

2

6

7

0

1

6

7

 

 

Worst case: Pivot only chops off one value

Best case: Pivot divides each array in half

44 of 53

Can we do better?

  • How to avoid hitting the worst case?
    • It all comes down to the pivot. If the pivot divides each array in half, we get better behavior

​

  • Here are four options for finding a pivot. What are the tradeoffs?
    • Just take the first element
    • Take the median of the full array
    • Take the median of the first, last, and middle element
    • Pick a random element

​

​

45 of 53

Strategies for Choosing a Pivot

  •  

Most commonly used

46 of 53

Quick Sort (v2: In-Place)

0

1

2

3

4

5

6

7

8

9

8

1

4

9

0

3

5

2

7

6

0

1

2

3

4

5

6

7

8

9

6

1

4

9

0

3

5

2

7

8

Low

X < 6

High

X >= 6

0

1

2

3

4

5

6

7

8

9

6

1

4

2

0

3

5

9

7

8

Low

X < 6

High

X >= 6

0

1

2

3

4

5

6

7

8

9

5

1

4

2

0

3

6

9

7

8

PIVOT?

PIVOT?

PIVOT?

PIVOT!

Select a pivot

Move pivot out of the way

Bring low and high pointers together, swapping elements if needed

Meeting point is where pivot belongs; swap in. Now recurse on smaller portions of same array!

Divide

47 of 53

Quick Sort (v2: In-Place)

quickSort(list) {

if (list.length == 1):

return list

else:

pivot = choosePivot(list)

smallerPart, largerPart = partition(pivot, list)

smallerPart = quickSort(smallerPart)

largerPart = quickSort(largerPart)

return smallerPart + pivot + largerPart

}

Worst case runtime?

​

​

Best case runtime?

​

In-practice runtime?

​

Stable?

​

In-place?

No

Yes

 

 

 

 

 

0

1

2

3

4

5

0

3

6

9

7

8

choosePivot:

- Use one of the pivot selection strategies

partition:

  • For in-place Quick Sort, series of swaps to build both partitions at once
  • Tricky part: moving pivot out of the way and moving it back!
  • Similar to Merge Sort divide step: two pointers, only move smaller one

48 of 53

Can we do better?

We’d really like to avoid hitting the worst case.

​

Key to getting a good running time, is always cutting the array (about) in half.

How do we choose a good pivot?

​

  • Here are four options for finding a pivot. What are the tradeoffs?
    • Just take the first element
    • Take the median of the first, last, and middle element
    • Take the median of the full array
    • Pick a random element as a pivot

​

​

CSE 373 19 SU - ROBBIE WEBER

48

49 of 53

Pivots

  •  

CSE 373 19 SU - ROBBIE WEBER

49

Median of three is a common choice in practice

50 of 53

Sorting: Summary

​

Best-Case

Worst-Case

Space

Stable

Selection Sort

Θ(n2)

Θ(n2)

Θ(1)

No

Insertion Sort

Θ(n)

Θ(n2)

Θ(1)

Yes

Heap Sort

Θ(nlogn)

Θ(nlogn)

Θ(n)

No

In-Place Heap Sort

Θ(nlogn)

Θ(nlogn)

Θ(1)

No

Merge Sort

Θ(nlogn)

Θ(nlogn)

Θ(nlogn)

Θ(n)* optimized

Yes

Quick Sort

Θ(nlogn)

Θ(n2)

Θ(n)

No

In-place Quick Sort

Θ(nlogn)

Θ(n2)

Θ(1)

No

What does Java do?

  • Actually uses a combination of 3 different sorts:
    • If objects: use Merge Sort* (stable!)
    • If primitives: use Dual Pivot Quick Sort
    • If “reasonably short” array of primitives: use Insertion Sort
      • Researchers say 48 elements

​

Key Takeaway: No single sorting algorithm is “the best”!

  • Different sorts have different properties in different situations
  • The “best sort” is one that is well-suited to your data

​

​

* They actually use Tim Sort, which is very similar to Merge Sort in theory, but has some minor details different

51 of 53

Insertion Sort

STRATEGY 1:

ITERATIVE IMPROVEMENT

STRATEGY 2:

IMPOSE STRUCTURE

STRATEGY 3:

DIVIDE AND CONQUER

Selection Sort

Heap Sort

Merge Sort

Quick Sort

WORST

BEST

 

STABLE

IN-PLACE

IN-PLACE

IN-PLACE

IN-PLACE

STABLE

 

WORST

BEST

WORST

BEST

WORST

BEST

 

 

WORST

BEST

 

 

 

 

 

 

Minimizes array writes, otherwise never preferred.

Simple, stable, low-overhead, great if already sorted.

Always good runtimes

Stable, very reliable! In-place variant is slower.

Fastest in practice (constant factors), bad worst case.

 

SPACE

 

SPACE

 

SPACE

 

SPACE

 

SPACE

52 of 53

Insertion Sort

STRATEGY 1:

ITERATIVE IMPROVEMENT

STRATEGY 2:

IMPOSE STRUCTURE

STRATEGY 3:

DIVIDE AND CONQUER

Selection Sort

Heap Sort

Merge Sort

Quick Sort

WORST

BEST

 

STABLE

IN-PLACE

IN-PLACE

IN-PLACE

IN-PLACE

STABLE

 

WORST

BEST

WORST

BEST

WORST

BEST

 

 

WORST

BEST

 

 

 

 

 

 

Minimizes array writes, otherwise never preferred.

Simple, stable, low-overhead, great if already sorted.

Always good runtimes

Stable, very reliable! In-place variant is slower.

Fastest in practice (constant factors), bad worst case.

 

SPACE

 

SPACE

 

SPACE

 

SPACE

 

SPACE

Can we do better than n log n?

  • For comparison sorts, NO. A proven lower bound!
    • Intuition: n elements to sort, no faster way to find “right place” than log n
  • However, niche sorts can do better in specific situations!

Many cool niche sorts beyond the scope of 373!

Radix Sort (Wikipedia, VisuAlgo) - Go digit-by-digit in integer data. Only 10 digits, so no need to compare!

Counting Sort (Wikipedia)

Bucket Sort (Wikipedia)

External Sorting Algorithms (Wikipedia) - For big data™

53 of 53

But Don’t Take it From Me…

​

​

​

DANCE EDITION

Here are some excellent visualizations for the sorting algorithms we’ve talked about!

Comparing Sorting Algorithms

​

​

Comparing Sorting Algorithms