Dynamic programming
Dynamic programming
• Characterize the structure of an optimal solution. (Define subproblem.)
• Recursively define the value of an optimal solution. (Express solutions
to subproblems recursively.)
• Compute the value of an optimal solution (in right order.)
• Construct an optimal solution from computed information.
Chain matrix multiplication
• Suppose that we want to multiply four matrices, A × B × C × D, of
dimensions 50 × 20, 20 × 1, 1 × 10, and 10 × 100, respectively.
• How many ways can < A, B, C, D> be fully parenthesized?
– (A( B(C D )))
– (A((BC )D))
– ((AB) (CD))
– ((A(BC ))D)
– (((AB)C )D)
Matrix multiplication
MATRIX-MULTIPLY(A, B)
if columns[A] ≠ rows[B]
then error “imcompatible dimensions”
else for i←1 to rows[A]
do for j←1 to columns[B]
do C[i,j] ← 0
for k←1 to columns[A]
do C[i,j] ← C[i,j] +A[i,k]⋅B[k,j]
return C
A : p×q matrix, B : q×r matrix, C = AB : p×r matrix
Time to compute C : pqr
Chain matrix multiplication
• Suppose that we want to multiply four matrices, A × B × C × D, of
dimensions 50 × 20, 20 × 1, 1 × 10, and 10 × 100, respectively.
• The order of multiplications makes a big difference in running time.
• Greedy approach (choose the cheapest multiplication) does not work.
(case 2 above)
• Problem : How do we determine the optimal order, if we want to
compute A1 × A2 × … × An where the Ai’s are matrices with
dimensions m0 × m1 , m1 × m2 ,…, mn-1 × mn , respectively?
Number of parenthesizations
• P(n) = # of alternative parenthesizations of a sequence of n matrices
• n=1:1
• n>1:
– a fully parenthesized matrix product is the product of two fully parenthesized
matrix subproducts
– the split between the two subproducts may occur between the kth and (k+1)th
matrices for any k=1, 2,…, n-1.
n
Show that P(n) is Ω(2 ) using substitution method.
• A particular parenthesization can be represented by a binary tree
– the individual matrices correspond to the leaves
– the root is the final product
– intermediate nodes are intermediate products.
• The possible orders to do the multiplication = the various full binary
trees with n leaves whose number is exponential in n.
Optimal substructure
• For a tree to be optimal, its subtrees must also be optimal.
• What are the subproblems corresponding to the subtrees? – products of
the form Ai × Ai+1 × … × Aj
• Define C(i, j) = minimum cost of multiplying Ai × Ai+1 × … × Aj
for 1 ≤ i ≤ j ≤ n.
• The size of the subproblem C(i, j) = number of matrix multiplications
= j–i
• Base case - the smallest subproblem : when i = j, C(i, j) = 0.
Optimal substructure
• For j > i, consider the optimal subtree for C(i, j).
• Suppose that an optimal subtree of AiAi+1…Aj splits the product
between Ak and Ak+1. ( i ≤ k < j )
• Then the subtrees of AiAi+1…Ak and Ak+1Ak+2…Aj within this optimal
subtree of AiAi+1…Aj must be optimal subtrees of AiAi+1…Ak and
Ak+1Ak+2…Aj, respectively.
• The cost of the subtree is then the cost of these two partial products +
the cost of combining them: C(i, k) + C(k + 1, j) +mi-1 ⋅ mk ⋅ mj
• Need to find the splitting point k for which this is smallest:
C(i, j ) = min{
i≤k<j
C(i,k) + C(k+1,j) + mi-1 ⋅ mk ⋅ mj }
Recursion tree for C(1,4)
Algorithm
• s : problem size
• Two-dimensional table, each entry takes O(n) time : O(n3) overall
running time.
• How can we reconstruct the optimal parenthesization?
Optimal binary search trees
• Suppose we know the frequency with which keywords occur in
programs of a certain language, for instance:
• We want to organize them in a binary search tree, so that the keyword
in the root is alphabetically bigger than all the keywords in the left
subtree and smaller than all the keywords in the right subtree.
Optimal binary search trees
• Input: n keys (in sorted order); frequencies of these keys: p1, p2,…, pn.
• Output: The binary search tree of lowest cost (= the expected number
of comparisons in looking up a key).
• Observations :
– Optimal BST might not have smallest height
– Optimal BST might not have highest-probability key at root.
• Build by exhaustive checking?
– Construct each n-node BST
– For each, put in keys
– Then compute expected search cost
– There are Ω(4n / n3/2 ) different BSTs with n nodes.
Optimal substructure
• Consider any subtree of a BST. It contains keys in a contiguous range
ki, …, kj for some 1 ≤ i ≤ j ≤ n.
T'
If T is an optimal BST and T contains subtree T' with keys ki, …, kj, then T' must
be an optimal BST for ki, …, kj.
Proof : cut and paste.
Using optimal substructure
• Given keys ki, …, kj (the problem)
• One of them, kr ,where i ≤ r ≤ j, must be the root.
• Left subtree of kr contains ki, …, kr-1
• Right subtree of kr contains kr+1, …, kj
If we
• examine all candidate roots kr , for i ≤ r ≤ j, and,
• determine all optimal BSTs containing ki, …, kr-1 and containing kr+1,
…, kj
then we’re guaranteed to find an optimal BST for ki, …, kj
Recursive solution
Subproblem domain :
• Find optimal BST for ki, …, kj , where i ≥1, i -1 ≤ j ≤ n
• When j = i -1, the tree is empty.
Define e[i,j] = expected search cost of optimal BST for ki, …, kj
If j = i -1, then e[i,j] = 0
If j ≥ i,
• Select a root kr, for some i ≤ r ≤ j
• make an optimal BST with ki, …, kr-1 as the left subtree.
• make an optimal BST with kr+1, …, kj as the right subtree.
• When a subtree becomes a subtree of a node :
– depth of every node in subtree goes up by 1.
j
w(i, j ) = ∑ pl
– expected search cost increases by
l =i
Recursive solution
• If kr is the root of an optimal BST for ki, …, kj :
• e[i,j] = pr + (e[i,r-1] + w(i,r-1)) + (e[r+1,j] + w(r+1,j))
• w(i,j) = w(i,r-1) + pr + w(r+1,j)
• e[i,j] = e[i,r-1] + e[r+1,j] + w(i,j)
0 if j = i-1
e[i,j] =
min{ e[i,r-1] + e[r+1,j] + w(i,j) } if i ≤ j
i≤r ≤ j
Computing an optimal solution
• Need 3 tables :
– e[1..n+1,0..n]
– root[i, j] : root of subtree with keys ki, …, kj
– w[1..n+1, 0..n]
OPTIMAL-BST(p, n)
for i=1 to n+1
do e[i, i-1] = 0
w[i, i-1] = 0
for l = 1 to n
do for i = 1 to n-l+1
do j = i+l-1
e[i, j] = ∞
w[i, j] = w[i, j-1] + pj
for r = i to j
do t = e[i, r-1] + e[r+1, j] + w[i, j]
if t < e[i, j]
then e[i, j] = t
root[i, j] = r
return e and root