CS2040S

Data Structures and Algorithms

Dynamic Programming
Riddle of the Week: The Travelling SalesPeople
Three travelers show up at a hotel where a room costs $300. They each pay
$100 and go to their room.

The manager realizes there is a special sale and the room only costs $250. He
gives his assistant $50 to return to the travelers. The assistant only has tens for
change, and so gives each traveler $10 in change, keeping $20 for himself.

So each traveler paid $90, and the assistant kept $20, leading to a total of
3*90+20 = 290 dollars. What happened to the remaining 10 dollars?
Semester Roadmap
Where are we?
– Searching
– Sorting
You are here
– Lists
– Trees
– Hash Tables
– Graphs
– Dynamic Programming
Roadmap
Today and Monday: Dynamic Programming
– Basics of DP
– Example: Longest Increasing Subsequence
– Example: Bounded Prize Collecting
– Example: Vertex Cover on a Tree
– Example: All-Pairs Shortest Paths
Dynamic Programming Basics
Dynamic Programming Basics
Optimal sub-structure:
Optimal solution can be constructed from optimal
solutions to smaller sub-problems.

Big Problem
Solution Merge

Small Small
Problem Small Problem
Problem
 Which of these problems exhibit optimal
sub-structure? (Choose all that apply.)
1. Sorting
2. Reversing a string
3. Merging two arrays
4. Shortest paths
5. Minimum spanning tree

is open
Optimal Sub-structure
Property of (nearly) every problem we study:
– Greedy algorithms
• Dijkstra’s Algorithm
• Minimum Spanning Tree algorithms

– Divide-and-conquer algorithms
• MergeSort
• Fast Fourier Transform
Source: Wikipedia
Optimal Sub-structure
Property of (nearly) every problem we study:
– Greedy algorithms
• Dijkstra’s Algorithm
• Minimum Spanning Tree algorithms

– Divide-and-conquer algorithms
• MergeSort
• Fast Fourier Transform
Dynamic Programming
Optimal substructure (simple case):
Dynamic Programming
Optimal substructure (overlapping sub-problems):
The same smaller problem is used to solve multiple
different bigger problems.
Dynamic Programming
Overlapping sub-problems:
The same smaller problem is used to solve multiple
different bigger problems.
Dynamic Programming
Contrast: Both have optimal substructure

No overlapping subproblems Overlapping subproblems

Divide-and-Conquer Dynamic Programming

Dynamic Programming
Basic strategy: (bottom up dynamic programming)

Step 4: solve root problem

Step 3: combine smaller problems

Step 2: combine smaller problems

Step 1: solve smallest problems

Dynamic Programming
Basic strategy: (DAG + topological sort)

Step 1: Topologically sort DAG

Step 2: Solve problems in reverse order

Dynamic Programming
Basic strategy: (top down dynamic programming)

Step 1: Start at root and recurse.

Step 2: Recurse.

Step 3: Recurse.

Step 4: Solve and memoize.

Only compute each
solution once.
Dynamic Programming
Table view:

a b c d e f g h i j k l m n o p
1 17 22 14 19 8 4 9 12 15 7 5 9 13 14 18 4
2 15 12 13 13 7
3
4
5
6
7
8
9
10
11
Dynamic Programming
Contrast: Both have optimal substructure

No overlapping subproblems Overlapping subproblems

Divide-and-Conquer Dynamic Programming

Roadmap
Today and Monday: Dynamic Programming
– Basics of DP
– Example: Longest Increasing Subsequence
– Example: Bounded Prize Collecting
– Example: Vertex Cover on a Tree
– Example: All-Pairs Shortest Paths
Longest Increasing Subsequence
Input: Sequence of integers
– Example: {8, 3, 6, 4, 5, 7, 7}

Output: Increasing subsequence

– Example: {8, 3, 6, 4, 5, 7, 7}

Goal: Output sequence of maximum length

– Example: {8, 3, 6, 4, 5, 7, 7}
Longest Increasing Subsequence
Input: Sequence of integers
– Example: {8, 3, 6, 4, 5, 7, 7}

Output: Length of increasing subsequence

– Example: 3 à {8, 3, 6, 4, 5, 7, 7}

Goal: Output sequence of maximum length

– Example: 4 à{8, 3, 6, 4, 5, 7, 7}
DAG Solution

8 3 6 4 5 7 7
DAG Solution

8 3 6 4 5 7 7
DAG Solution

8 3 6 4 5 7 7
DAG Solution

8 3 6 4 5 7 7
DAG Solution

8 3 6 4 5 7 7
DAG Solution

8 3 6 4 5 7 7

Step 1: Topological sort. (Oops, nothing to do.)

DAG Solution

8 3 6 4 5 7 7
1. LP(8) = 0

Step 2: Calculate longest paths.

DAG Solution

8 3 6 4 5 7 7
2. LP(3) = 3

Step 2: Calculate longest paths: DAG_SSSP.

DAG Solution

8 3 6 4 5 7 7
2. LP(3) = 3

Relax edges
in toposort order…

Step 2: Calculate longest paths: DAG_SSSP.

DAG Solution

7. LP(7) = 0

8 3 6 4 5 7 7
1. LP(8) = 0 2. LP(3) = 3

6. LP(7) = 0
3. LP(6) = 1

4. LP(4) = 2

5. LP(5) = 1

Step 2: Calculate longest paths. LIS = max(LP)+1

 What is the running time of the DAG alg for
a sequence of n numbers?
1. O(n)
2. O(n log n)
3. O(n2)
4. O(n2 log n)
5. O(n3)
6. None of the above.

is open
 DAG Solution V = list of numbers
|V| = n
|E| = (n + n-1 + n-2 + …)

7. LP(7) = 0

8 3 6 4 5 7 7
1. LP(8) = 0 2. LP(3) = 3

6. LP(7) = 0
3. LP(6) = 1

4. LP(4) = 2

5. LP(5) = 1
Longest path: O(V + E) = O(n2)

Run longest path n times = O(n3)

Overlapping Subproblems

8 3 6 4 5 7 7
Overlapping Subproblems

8 3 6 4 5 7 7
1. LP(7) = 0

Start with the smallest sub-problem: LP(7)

Overlapping Subproblems

2. LP(7) = 0

8 3 6 4 5 7 7
1. LP(7) = 0

Start with the smallest sub-problem: LP(7)

Overlapping Subproblems

2. LP(7) = 0

8 3 6 4 5 7 7
3. LP(5) = 0 + 1 1. LP(7) = 0

Calculate LP(5):
• Examine each outgoing edge.
• Find the maximum.
• Add 1.
Overlapping Subproblems

4. LP(4) = max(1, 0, 0) + 1
2. LP(7) = 0

8 3 6 4 5 7 7
3. LP(5) = 1 1. LP(7) = 0

Calculate LP(4):
• Examine each outgoing edge.
• Find the maximum.
• Add 1.
Overlapping Subproblems

4. LP(4) = 2 2. LP(7) = 0

8 3 6 4 5 7 7
3. LP(5) = 1 1. LP(7) = 0

5. LP(6) = 1

Calculate LP(6):
• Examine each outgoing edge.
• Find the maximum.
• Add 1.
Overlapping Subproblems

4. LP(4) = 2 2. LP(7) = 0

8 3 6 4 5 7 7
5. LP(6) = 1 3. LP(5) = 1 1. LP(7) = 0

6. LP(3) = max(1, 2, 1, 0, 0) + 1 = 3

Calculate LP(3):
• Examine each outgoing edge.
• Find the maximum.
• Add 1.
Longest Increasing Subsequence
Input:
– Array A[1..n]

Define sub-problems:
– S[i] = LIS(A[i..n]) starting at A[i]

Example: {8, 3, 6, 4, 5, 7, 7}
– S[5] = 2 à {8, 3, 6, 4, 5, 7, 7}
– S[2] = 4 à {8, 3, 6, 4, 5, 7, 7}
Dynamic Programming
Table view:

Entry Longest path that

starts at entry X
7 0

7 0

5 …

8
Longest Increasing Subsequence
Input:
– Array A[1..n]

Define sub-problems:
– S[i] = LIS(A[i..n]) starting at A[i]

Solve using sub-problems:

– S[n] = 0
– S[i] = (max(i,j) Î E S[j]) + 1
Dynamic Programming Recipe
Step 1: Identify optimal substructure
E.g., LIS can be built from suffix LIS

Step 2: Define sub-problems

E.g., S[i] = LIS(A[i..n]) starting at A[i]

Step 3: Solve problem using sub-problems

E.g., S[i] = (max(i,j) Î E S[j]) + 1

Step 4: Write (pseudo)code.

Overlapping Subproblems

4. LP(5) = 2 2. LP(7) = 0

8 3 6 4 5 7 7
5. LP(6) = 1 3. LP(5) = 1 1. LP(7) = 0

6. LP(2) = max(1, 2, 1, 0, 0) + 1 = 3

Calculate LP(2):
• Examine each outgoing edge.
• Find the maximum.
• Add 1.
Longest Increasing Subsequence
LIS(V): // Assume graph is already topo-sorted
int[] S = new int[[Link]]; // Create memo array
for (i=0; i<[Link]; i++) S[i] = 0; // Initialize array to zero
S[n-1] = 1; // Base case: node V[n-1]
for (int v = [Link]-2; v>=0; v--) {
int max = 0; // Find maximum S for any outgoing edge
for (Node w : [Link]()) { // Examine each outgoing edge
if (S[w] > max) max = S[w]; // Check S[w], which we already
// calculated earlier.
}
S[v] = max + 1; // Calculate S[v] from max of outgoing edges.
}
Longest Increasing Subsequence
Input: Let’s stop thinking about
this as a graph…
– Array A[1..n]

Alternate definition:
– S[i] = LIS(A[1..i]) ending at A[i]

Example: {8, 3, 6, 4, 5, 7, 7}
– S[4] = 2 à {8, 3, 6, 4, 5, 7, 7}
– S[5] = 3 à {8, 3, 6, 4, 5, 7, 7}
Longest Increasing Subsequence
Input: Let’s stop thinking about
this as a graph…
– Array A[1..n]

Alternate definition:
– S[i] = LIS(A[1..i]) ending at A[i]

Solve using sub-problems:

– S[1] = 0
– S[i] = (max(j < i, A[j] < A[i]) S[j]) + 1
Longest Increasing Subsequence
LIS(A):
int[] S = new int[[Link]]; // Create memo array
for (i=0; i<[Link]; i++) S[i] = 0; // Initialize array to zero
S[0] = 1; // Base case: length 1
for (int i = 0; i<[Link]; i++) {
int max = 0; // Find maximum S for any preceding node
for (int j=0; j<i; j++) { // Examine each preceding element in the sequence
if (A[j] < A[i]) // If A[i] is bigger than A[j]
if (S[j] > max)
max = S[j]; // If S[j] is longer sequence
}
S[i] = max + 1; // Calculate S[i] from max of preceding elements.
}
 What is the running time of the LP-LIS alg
for a sequence of n numbers?
1. O(n)
2. O(n log n)
3. O(n2)
4. O(n2 log n)
5. O(n3)
6. None of the above.

is open
Longest Increasing Subsequence
LIS(A):
int[] S = new int[[Link]]; // Create memo array
for (i=0; i<[Link]; i++) S[i] = 0; // Initialize array to zero
S[0] = 1; // Base case: length 1
for (int i = 0; i<[Link]; i++) {
int max = 0; // Find maximum S for any preceding node
for (int j=0; j<i; j++) { // Examine each preceding element in the sequence
if (A[j] < A[i]) // If A[i] is bigger than A[j]
if (S[j] > max)
max = S[j]; // If S[j] is longer sequence
}
S[i] = max + 1; // Calculate S[i] from max of preceding elements.
}
Longest Increasing Subsequence
Summary:
Greedy subproblems: S[i] = LIS(A[1..i])
• n subproblems
• Subproblem i takes takes time O(i)

Total time: O(n2)

Challenge of the Day:

How do you solve LIS in time O(n log n)?

Hint: use binary search to solve subproblems faster.

Roadmap
Today and Monday: Dynamic Programming
– DP Basics
– Longest Increasing Subsequence
– Prize Collecting
– Vertex Cover on a Tree
– All-Pairs-Shortest-Paths
Prize Collecting
Input:
– Directed Graph G = (V,E)
– Edge weights w = prizes on each edge

-4
7
-11

-3 2
1
-10 1 -3
-6
3
-5
Prize Collecting
Output:
– Prize collecting path
– Example: 7 + 2 + 1 = 10

-4 7
-11

-3 1 2
-10 1 -3
-6
3
-5
 What is the maximum prize?

1. 1 -4 7
-11
2. 3 2
-3 1
3. 10 -10 -3
1
-6
4. 15
3
5. 17 -5

6. Infinite

is open
Prize Collecting
Output:
– Prize collecting path: 7 + 2 + 1 - 5 + 3 - 3 - 4 = 1
– Positive weight cycle à infinite prizes!

-4
7
-11

-3 1 2
-10 1 -3
-6
3
-5
Prize Collecting
Aside: How could we determine if there is a
positive weight cycle in a graph?

-4
7
-11

-3 1 2
-10 1 -3
-6
3
-5
Prize Collecting
1. Check for positive weight cycles.
2. Negate the edges, run BF.

-4
7
-11

-3 1 2
-10 1 -3
-6
3
-5
Lazy Prize Collecting
Input:
– Graph G = (V,E)
– Edge weights w = prizes on each edge
– Limit k: only cross at most k edges

-4 7
-11

-3 1 2
-10 1 -3
-6
3
-5
Lazy Prize Collecting
Example:
– k=1à7
– k=2à9
– k = 3 à 10
– … -4 7
– k = 71 à 17 -11

-3 1 2
-10 1 -3
-6
3
-5
Lazy Prize Collecting
Note: Not a shortest path problem
– Not a shortest path problem! Longest path…
– Negative weight cycles.
– Positive weight cycles.

-4 7
-11

-3 1 2
-10 1 -3
-6
3
-5
Lazy Prize Collecting
Idea 1:
– Transform G into a DAG

-4 7
-11

-3 1 2
-10 1 -3
-6
3
-5
Lazy Prize Collecting
Idea 1:
– Transform G into a DAG
– Make k copies of every node: (v,1), (v,2), (v,3), …

-4 7
-11

-3 1 2
-10 1 -3
-6
3
-5
Lazy Prize Collecting
Idea 1:
– Transform G into a DAG
– Make k copies of every node: (v,1), (v,2), (v,3), …

v v

w z
w

z
k=2 k=1 k=0
Lazy Prize Collecting
Idea 1:
– Transform G into a DAG
– Make k copies of every node: (v,1), (v,2), (v,3), …

v v

w z
w

z
k=2 k=1 k=0
Lazy Prize Collecting
Idea 1:
– Transform G into a DAG
– Make k copies of every node: (v,1), (v,2), (v,3), …
– Solve prize collecting via DAG_SSSP (longest path)

v v
-2 -2 6
-2

w 6 6 z
5 w
5 5
z
k=2 k=1 k=0
Lazy Prize Collecting
Idea 1:
– Transform G into a DAG
– Make k copies of every node: (v,1), (v,2), (v,3), …
– Solve longest-path problem for each source.

-4 7
-11

-3 1 2
-10 1 -3
-6
3
-5
 What is the running time of Idea 1?

1. O(E)
2. O(VE)
3. O(kE)
4. O(kVE)
5. O(kV2E)
6. None of the above
Lazy Prize Collecting
Running Time:
– Transformed graph: kV nodes, kE edges
– Topo-sort / Longest path: O(kV + kE)
– Once per source: repeat V times è O(kVE)?

-4 7
-11
Whenever you transform
-3 1 2
a graph, do NOT forget
to recompute the number -10 -3
1
of nodes and edges in -6
the new graph.
3
-5
Lazy Prize Collecting
Running Time:
– Transformed graph: kV nodes, kE edges
– Topo-sort / Longest path: O(kV + kE)
– Create super-source….

0
0

0
Lazy Prize Collecting
Idea 2: Dynamic Programming
If you know the optimal solution for (k-1), then it is
easy to computer optimal solution for k.

-4 7
-11

-3 1 2
-10 1 -3
-6
3
-5
Dynamic Programming Recipe
Step 1: Identify optimal substructure
E.g., solution for (k-1) è solution for k

Step 2: Define sub-problems

Step 3: Solve problem using sub-problems

Step 4: Write (pseudo)code.

Lazy Prize Collecting
Idea 2: Dynamic Programming
P[v, k] = maximum prize that you can collect starting
at v and taking exactly k steps.

-4 7
Modified subproblem: -11
Leads to better
optimal substructure. -3 1 2
-10 1 -3
Often, useful to solve -6
modified problem.
3
-5
 P(v, 0) = ?? v
-4 7
-11
1. 0
-3 2
2. 2 1
-10 1 -3
3. -3 -6
4. 4 3
-5
5. 5

is open
Lazy Prize Collecting
Idea 2: Dynamic Programming
P[v, k] = maximum prize that you can collect starting
at v and taking exactly k steps.
P[v, 0] = 0

-4 7
-11

-3 1 2
-10 1 -3
-6
3
-5
Lazy Prize Collecting
Idea 2: Dynamic Programming
P[v, k] = maximum prize that you can collect
starting at v and taking exactly k steps.

Solve P[v,k] using subproblems:

P[v, k] = MAX { P[w1, k-1] + w(v, w1),
P[w2, k-1] + w(v, w2),
P[w3, k-1] + w(v, w3), … }

where [Link]() = {w1, w2, w3, …}

Lazy Prize Collecting
Idea 2: Dynamic Programming
P[v, 1] = max(0+2, 0-3) = 2

-4 7
-11

-3 1 2
-10 1 -3
-6
3
-5
Lazy Prize Collecting
Idea 2: Dynamic Programming
P[v, 1] = max(0+2, 0-3) = 2
P[v, 2] = max(1+2, -5-3) = 3

-4 7
-11

-3 1 2
-10 1 -3
-6
3
-5
Lazy Prize Collecting
Idea 2: Dynamic Programming
P[v, 1] = max(0+2, 0-3) = 2
P[v, 2] = max(1+2, -5-3) = 3
P[v, 3] = max(-4+2, -2-3) = -2

-4 7
-11

-3 1 2
-10 1 -3
-6
3
-5
Lazy Prize Collecting
Idea 2: Dynamic Programming
When is it worth crossing a negative edge?

-4 7
-11

-3 1 2
-10 1 -3
-6
3
-5
Dynamic Programming
Table view: P[k, v]

k v1 v2 v3 v4 v5 v6 v7 v8 v9 v10

1 17 22 14 19 8 4 9 12 15 7
2 15 12 13 13 7
3
4
5
6
7
8
9
10
11
int LazyPrizeCollecting(V, E, kMax) {

int[][] P = new int[[Link]][kMax+1]; // create memo table P

for (int i=0; i<[Link]; i++) // initialize P to zero
for (int j=0; j<kMax+1; j++)
P[i][j] = 0;

for (int k=1; k<kMax+1; k++) { // Solve for every value of k

for (int v = 0; v<[Link]; v++) { // For every node…
int max = -INFTY;
// …find max prize in next step
for (int w : V[v].nbrList()) {
if (P[w,k-1] + E[v,w] > max)
max = P[w,k-1] + E[v,w];
}
P[v, k] = max;
}
}
return maxEntry(P); // returns largest entry in P
}
Lazy Prize Collecting
Idea 2: Dynamic Programming
P[v, k] = maximum prize that you can collect starting
at v and taking exactly k steps.

Total Cost:
Two factors:
– Number of subproblems: kV
– Cost to solve each subproblem: |[Link]|

Total: O(kV2)
Dynamic Programming
Table view: P[k, v]

k v1 v2 v3 v4 v5 v6 v7 v8 v9 v10

1 17 22 14 19 8 4 9 12 15 7
2 15 12 13 13 7
3
4
5
6
7
8
9
10
11
Lazy Prize Collecting
Idea 2: Dynamic Programming
P[v, k] = maximum prize that you can collect starting
at v and taking exactly k steps.

Total Cost:
Two factors:
– Number of rows: k
– Cost to solve all problems in a row: E

Total: O(kE)
Roadmap
Today and Monday: Dynamic Programming
– DP Basics
– Longest Increasing Subsequence
– Prize Collecting
– Vertex Cover on a Tree
– All-Pairs-Shortest-Paths