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.
1. Run Bellman-Ford once to compute d(v).
2. Problem equivalent to using
ℓ’(u,w) = ℓ(u,w)+d(u)-d(w) ≥ 0.
3. Run Dijkstra from every source.
Runtime: O(|V||E|+|V|2log|V|)