Announcements
Announcements
Homework 5 Due on Friday
Slight correct to Q3: substring -> subsequence
Last Time
Dynamic Programs
Family of Subproblems
Recursion Relation
Tabulate and Solve
Proof of Correctness by Induction
Runtime: [#subproblems][time/subproblem]
Finding right subproblems is key
Today
Chain Matrix Multiplication
All-Pairs Shortest Paths
Chain Matrix Multiplication
How long does it take to multiply matrices?
Recall if C = A·B then
Cxz = Σ AxyByz.
Suppose A is an nxm matrix and B is mxk. Then for each entry of C (of which there are nk), we need to sum m terms.
Runtime O(nmk)*
*Can do slightly better with Strassen, but we’ll ignore this for now.
More than two Matrices
Next suppose that you want to multiply three matrices ABC.
Can do it two different ways,
A(BC) OR (AB)C.
How long does it take?
Example
A is 2×3,
B is 3×3,
C is 3×1.
A(BC)
3·3·1 = 9
2·3·1 = 6
Runtime: 9 + 6 = 15
(AB)C
2·3·3 = 18
2·3·1 = 6
Runtime: 18 + 6 = 24
Multiplication order matters!
Problem Statement
Problem: Find the order to multiply matrices A1, A2, A3,…,Am that requires the fewest total operations.
In particular, assume A1 is an n0 x n1 matrix, A2 is n1 x n2, generally Ak is an nk-1 x nk matrix.
Recursion
We need to find a recursive formulation.
Often we do this by considering the last step.
For some value of k, last step:
(A1A2…Ak)·(Ak+1Ak+2…Am)
Number of steps:
CMM(A1,A2,…,Ak) to compute first product
CMM(Ak+1,…,Am) to compute second product
n0nknm to do final multiply
Recursion CMM(A1,…,Am) =
mink[CMM(A1,…,Ak)+CMM(Ak+1,…,Am)+n0nknm]
Subproblems
What subproblems do we need to solve?
We cannot afford to solve all possible CMM problems.
CMM(A1,…,Am) requires CMM(A1,…,Ak) and CMM(Ak,…,Am).
These require CMM(Ai,Ai+1,…,Aj), but nothing else.
Only need subproblems C(i,j) = CMM(Ai,Ai+1,…,Aj) for 1 ≤ i ≤ j ≤ m.
Fewer than m2 total subproblems.
Critical: Subproblem reuse.
Full Recursion
Base Case: C(i,i) = 0.
(With a single matrix, we don’t have to do anything)
Recursive Step:
C(i,j) = mini≤k
O(|V|2)
O(|V|3)
O(log|V|) iterations
Runtime: O(|V|3log|V|)
Floyd-Warshall Algorithm
Label vertices v1, v2, …, vn.
Let dk(u,w) be the length of the shortest u-w path using only v1, v2,…,vk as intermediate vertices.
Base Case:
Recursion
Break into cases based on whether shortest path uses vk.
The shortest path not using vk has length
dk-1(u,w).
The shortest path using vk has length
dk-1(u,vk)+dk-1(vk,w).
u
w
vk
Algorithm
Base Case:
Recursion: For each u, w compute:
End Condition: d(u,w) = dn(u,w) where n = |V|.
O(|V|2)
O(|V|2)
O(|V|) Iterations
Runtime: O(|V|3)
Best Known Algorithm
Actually isn’t DP.
Run Bellman-Ford once to compute d(v).
Problem equivalent to using
ℓ’(u,w) = ℓ(u,w)+d(u)-d(w) ≥ 0.
Run Dijkstra from every source.
Runtime: O(|V||E|+|V|2log|V|)