Announcements
Announcements
HW 4 Due today
Today
Dynamic Programming Introduction
Dynamic Programming (Ch 6)
Background and past examples
Longest Common Subsequence
Knapsack
Chain Matrix Multiplication
All-Pairs Shortest Paths
Independent Sets of Trees
Travelling Salesman
Computing Fibonacci Numbers
Recall:
Fn = 1 if n = 0 or 1 .
Fn = Fn-1 + Fn-2 otherwise
Naïve Algorithm
Fib(n)
If n ≤ 1
Return 1
Else
Return Fib(n-1)+Fib(n-2)
Far too slow!
Improved Algorithm
Fib2(n)
Initialize A[0..n]
A[0] = A[1] = 1
For k = 2 to n
A[k] = A[k-1] + A[k-2]
Return A[n]
Tabulation of answers avoids runaway recursive calls.
Another Example
Something similar happens with our algorithm for shortest paths in DAGs.
This was based on the basic recursive formula
applied to vertices in topological order.
Example
s
A
B
C
D
t
dist(t)
dist(D)
dist(C)
dist(s)
dist(C)
dist(A)
dist(B)
dist(s)
dist(A)
dist(B)
dist(s)
dist(A)
dist(s)
dist(A)
dist(s)
dist(s)
dist(s)
dist(s)
Simplify by Tabulating
Instead of computing these values recursively, compute them one at a time, recording them. Then in the future, you only need to do table lookups.
Dynamic Programming
Our final general algorithmic technique:
Break problem into smaller subproblems.
Find recursive formula solving one subproblem in terms of simpler ones.
Tabulate answers and solve all subproblems.
Question: Dynamic Program
Which of the following algorithms that we have covered so far involves a dynamic program?
Bellman-Ford
Optimal Caching
Computing SCCs
Closest Pair of Points
Karatsuba Multiplication
Subsequences
Given a sequence, say ABCBA, a subsequence is the sequence obtained by deleting some letters and leaving the rest in the same order.
For example, ABCBA would have a subsequence ABCBA = ACB.
Longest Common Subsequence
We say that a sequence is a common subsequence of two others, if it is a subsequence of both.
For example ABC is a common subsequence of ADBCA and AABBC.
Problem: Given two sequences compute the longest common subsequence. That is the subsequence with as many letters as possible.
Question: LCSS
What is the length of the longest common subsequence of ABCBA and ABACA?
1
2
3
4
5
ABCA = ABCBA = ABACA
Case Analysis
How do we compute LCSS(A1A2…An, B1B2…Bm)?
Consider cases for the common subsequence:
It does not use An.
It does not use Bm.
It uses both An and Bm and these characters are the same.
Case 1
If the common subsequence does not use An, it is actually a common subsequence of
A1A2…An-1, and B1B2…Bm
Therefore, in this case, the longest common subsequence would be
LCSS(A1A2…An-1, B1B2…Bm).
Case 2
If the common subsequence does not use Bm, it is actually a common subsequence of
A1A2…An, and B1B2…Bm-1
Therefore, in this case, the longest common subsequence would be
LCSS(A1A2…An, B1B2…Bm-1).
Case 3
If a common subsequence uses both An and Bm…
These characters must be the same.
Such a subsequence is obtained by taking a common subsequence of:
A1A2…An-1, and B1B2…Bm-1
and adding a copy of An = Bm to the end.
The longest length of such a subsequence is
LCSS(A1A2…An-1, B1B2…Bm-1)+1.
Recursion
On the other hand, the longest common subsequence must come from one of these cases. In particular, it will always be the one that gives the biggest result.
LCSS(A1A2…An, B1B2…Bm) =
Max(LCSS(A1A2…An-1, B1B2…Bm),
LCSS(A1A2…An, B1B2…Bm-1),
[LCSS(A1A2…An-1, B1B2…Bm-1)+1])
[where the last option is only allowed if An = Bm]
Recursion
LCSS(A1…n,B1…m)
LCSS(A1…n-1,B1…m)
LCSS(A1…n,B1…m-1)
LCSS(A1…n-1,B1…m-1)
LCSS(A1…n-2,B1…m)
LCSS(A1…n-2,B1…m-1)
Key Point: Subproblem reuse
Only ever see LCSS(A1A2…Ak, B1B2…Bℓ)
Base Case
Our recursion also needs a base case.
In this case we have:
LCSS(∅,B1B2…Bm) = LCSS(A1A2…An,∅) = 0.
Algorithm
LCSS(A1A2…An,B1B2…Bm)
Initialize Array T[0…n,0…m]
\\ T[i,j] will store LCSS(A1A2…Ai,B1B2…Bj)
For i = 0 to n
For j = 0 to m
If (i = 0) OR (j = 0)
T[i,j] ← 0
Else If Ai = Bj
T[i,j] ← max(T[i-1,j],T[i,j-1],T[i-1,j-1]+1)
Else
T[i,j] ← max(T[i-1,j],T[i,j-1])
Return T[n,m]
O(nm) iterations
O(1)
Example
∅
A
AB
ABC
ABCB
ABCBA
∅ . . . .
A . . . .
AB . . .
ABA . .
ABAC.
ABACA
0
0
0
0
0
0
0
1
1
1
1
1
0
1
2
2
2
2
0
1
2
2
3
3
0
1
2
2
3
3
0
1
2
3
3
4
A
B
C
A
String:
ABCA
Proof of Correctness
Prove by induction that each value assigned to T[i,j] is the correct value for LCSS(A1A2…Ai,B1B2…Bj).
Base Case: When i or j is 0 we assign 0.
Inductive Step: Assuming that previous values are assigned correctly, T[i,j] gets correct value because of recursion for LCSS and inductive hypothesis (and that we have previously filled in T[i-1,j], T[i,j-1] and T[i-1,j-1]).
Notes about DP
General Correct Proof Outline:
Prove by induction that each table entry is filled out correctly
Use base-case and recursion
Runtime of DP:
Usually
[Number of subproblems]x[Time per subproblem]
More Notes about DP
Finding Recursion
Often look at first or last choice and see what things look like without that choice
Key point: Picking right subproblem
Enough information stored to allow recursion
Not too many