Algorithms: Sequential, Parallel and Distributed, Second Edition 9-1
Chapter 9
Dynamic Programming
At a Glance
Table of Contents
Algorithms: Sequential, Parallel and Distributed, Second Edition 9-2
Lecture Notes
Overview
In Chapter 9 we discuss the dynamic programming major design strategy. The principle of
optimality is introduced, and its role in determining a recurrence relation of an optimal solution
to an optimization problem is discussed. Dynamic programming solutions are given to the
problems of finding and optimal parenthesization for computing a chained matrix product,
finding an optimal binary search tree for a given set of keys and probabilities, and finding the
longest common subsequence of two character strings.
Chapter Objectives
After completing the chapter the student will know:
optimal binary search tree for a subset of the keys, usually must be explicitly maintained
(also using recurrence) in order to reconstruct the optimal solution whose value was
obtained by bottom-up recurrence resolution
Instructor Notes
A string matching problem related to the longest common subsequence contained in two
Algorithms: Sequential, Parallel and Distributed, Second Edition 9-3
Solutions to Selected Exercises
Section 9.1 Optimization Problems and the Principle of Optimality
9.1 Given i and j, let k be any intermediate city on a cheapest flight from i to j. Then the flight
from i to k must be a cheapest flight, and the flight from i to j must be a cheapest flight,
9.2 The principle of optimality for costliest trips fails to hold, in general. In fact, given three
cities a,b,c, suppose the cost of flying directly (either way) between a and c and b and c is 1,
9.3 Suppose we have coins of denominations d0 < d1 < … < dm. and we wish to make change
in the amount of C using the fewest number of coins. Of course, it may not be possible to make
change at all. For any i , 0 ≤ i ≤ m, let Si(x) denote the minimum number of coins required to
make change of x, where the only coins used have denominations {d0 , d1 , … , di}. We set
Si(x) = ∞ if we can not make change of x using coins of these denominations. Then Sm(C) is
must be made using a minimum number of such coins. In other words, we must have an
optimal solution S(C*), so that the principle of optimality holds.
As yet another interpretation, suppose we have an optimal solution using S(C) coins to the
problem, and we partition the coins into two subsets whose value adds up to C1 and C2
respectively. Then the solution to the two problems with change C1and C2, respectively must
9. 4. Given a 2-tree T with n leaves, we show that there is a unique paranthesization P for the
matrix product of M0, M1, … , Mn–1 such that T = T(P) using induction on n.
Basis step: n = 1 or 2. Trivial.
9.5 The following pseudocode is based directly on a top-down implementation of the
recurrence relation (9.2.2) of the text.
procedure ParenthesizeRec(d[0:n], i, j) recursive
Input: d[0:n] (an array of dimensions for a chained matrix product)
i, j (integers such that 0 ≤ i ≤ j ≤ n – 1)
ParenthesizeRec(d[0:n], k+1, j)
Temp ← m[i, k] + m[k+1, j] + d[i]*d[k+1]*d[j+1]
if min > Temp then
min ← Temp
TempCut ← k
9.6 Since OptimalParenthesization does the same amount of work for any input d[0:n], the
best-case, worst-case, and average complexities are all equal. Clearly, the number of additions,
multiplications and comparisons made in computing the output matrices m[0:n – 1, 0:n – 1] and
FirstCut[0:n – 1, 0:n – 1] is of the same order as the total number of assignments to the
variable Temp in the innermost loop. Therefore, we choose this assignment to Temp as the
).(
6
)12(
)1(2/)1(
2/)1(
32
1
1
2
1
1
n
n
nnnn
nnddn
n
t
n
d
−
−−−=
−−−=
−
=
−
=
9.7 Since matrices M0, M1, M2, M3, M4, have dimensions 67, 78, 83, 310,1 106,
respectively, d[0:5]=[6,7,8,3,10,6]. Letting mij denote the number of multiplications
performed using an optimal parenthesization of MiMi+1…Mj, and letting fij denote the
associated first cut, then employing recurrence relation (14.2.2), we have
mii = 0, i = 0, …, 4.
m24 = min{ m22 + m34 + d2d3d5 , m23 + m44 + d2d4d5}
= min{0+180+(8)(3)(6),336+0+(8)(10)(6)}
= min{324, 816} = 324, f24 = 2.
m03 = min{m00 + m13 + d0d1d4, m01 + m23 + d0d2d4, m02 + m33 + d0d3d4}
Algorithms: Sequential, Parallel and Distributed, Second Edition 9-6
* 0 168 378 474 * * 1 2 2
m = * * 0 240 324 FirstCut = * * * 2 2
* * * 0 180 * * * * 3
* * * * 0 * * * * *
Using the matrix FirstCut we can recursively construct the optimal parenthesization:
9.9 i 0 1 2 3
pi .4 .3 .2 .1
For convenience we let aij=A(Tij) and let rij denote the key of the root of tree Tij. By
convention we set
aij = 0, i > j.
´ all equal to zero we obtain
9.10 We have the following input to the optimal binary search tree problem
i 0 1 2 3 4 5
pi .2 .1 .2 .05 .05
qi .05 0 .25 0 .1 0
= 1.95, and r03 = 1 or 2
a14 = min{ a24 , a11 + a34, a12 + a44, a13} + σ(1,4) = min{1, .35 + .35, .9+.15, 1.2} + .75
= 1.45, and r14 = 2
.a04 = min{ a14 , a00 + a24, a01 + a34, a02 + a44, a03} + σ(0,4)
= min{1.45, .25 + 1, .85 + .35, 1.5 + .15, 1.95} + 1 = 2.2, and r04 = 2
.
9.11 a) The following is pseudocode for a recursive procedure OptTree for computing the
optimal binary search tree Tij for keys Ki<Ki+1<…<Kj from the two-dimensional array
Root[0:n – 1, 0:n – 1]. The array Root[0:n – 1, 0:n – 1] will be global to the procedure
OptTree. To obtain the optimal search tree for all the keys, we initially call procedure
OptTree with i = 1 and j = n.
9.12 a. Let p0, p1, … , pn-1,be any sequence of nonnegative probabilities such that for each i, 0
≤ i ≤ n – 1,
pi > pi+1 + pi+2 + … + pn-1, i = 0,1, …, n – 2 .
For example, choose pi = 2*3n–i/(3n – 1), i = 0,1, …, n – 2 .
Then, the resulting optimal search tree is completely right-skewed. The proof of this is a
Proof. We use induction on the number of keys.
Basis step: one key. Trivial.
Induction step: Assume the Proposition is true for binary search trees having fewer than n
keys, and consider a binary search tree T with n keys. According to the hypothesis, assign
the keys probabilities such that the probability of the key in each node is greater than the
9.13
a
l
g
o
r
i
t
h
m
s
LCS
0
1
2
3
4
5
6
7
8
9
10
0
0
0
0
0
0
0
0
0
0
0
0
a
1
0
1
1
1
1
1
1
1
1
1
1
l
2
0
1
2
2
2
2
2
2
2
2
2
l
3
0
1
2
2
2
2
2
2
2
2
2
i
4
0
1
2
2
2
2
3
3
3
3
3
g
5
0
1
2
3
3
3
3
3
3
3
3
a
6
0
1
2
3
3
3
3
3
3
3
3
t
7
0
1
2
3
3
3
3
4
4
4
4
o
8
0
1
2
3
4
4
4
4
4
4
4
r
9
0
1
2
3
4
5
5
5
5
5
5
9.14 An examination of the table in Figure 9.8 shows that all common subsequences end with
the suffix string “une”. There are three different strings forming the 3-character prefix
9.15 Given LCS[0:n – 1, 0:n – 1], we will satisfy ourselves with designing an algorithm that
computes a longest common (string) subsequence using the move left rule. In general, if all
Algorithms: Sequential, Parallel and Distributed, Second Edition 9-10
longest common subsquences were desired, when tracing back the dynamic programming
recurrence, one would have to check for a possibly new longest common subsequence
9.17 Suppose the sequence of n distinct numbers is stored in the array A[0: n – 1]. For 0 ≤ i ≤
j ≤ n – 1, let Len[i,j] denote the length of a longest increasing subsequence in A[i:j] with i
as the first term in the subsequence. We then have the following initial conditions:
Len[i, i] = 1 for 0 ≤ i ≤ n – 1,
Len[i, i + 1] = 2 if A[i + 1] > A[i],
Input: A[0: n – 1] (array of n distinct integers)
Output: LenLongIncrSubSeq (length of the longest increasing subsequence in A[0: n – 1])
for i ← 0 to n – 1 do
Len[i, i] ← 1
endfor
endfor
Len[j – m, j] ← max
endfor
endfor
LenLongIncrSubSeq ← Len[0: n – 1]
given in the exercise. We then have the following computation for Len[0:11, 0:11].
Algorithms: Sequential, Parallel and Distributed, Second Edition 9-12
45 23 9 3 99 108 76 12 77 16 18 4
j
i
0
1
2
3
4
5
6
7
8
9
10
11
0
1
1
1
1
2
3
3
3
3
3
3
3
1
1
1
1
2
3
3
3
3
3
3
3
2
1
1
2
3
3
3
3
3
4
4
3
1
2
3
3
3
3
3
4
4
4
1
2
2
2
2
2
2
2
5
1
1
1
1
1
1
1
6
1
1
2
2
3
3
7
1
2
2
3
3
8
1
1
1
1
9
1
1
2
10
1
1
11
1
Thus, we see that there are two longest increasing subsequences of length 4, one starting at 9,
namely 9, 12, 16, 18 and one starting at 3, 12, 16, 18.
Remarks. The computation of the matrix Len[0:n – 1, 0:n – 1] determines all the starting
points of longest increasing subsequences. However, there may be more than one longest
9.18 Consider the knapsack problem with objects{b0, b1, … , bn-1} having positive integer
values v0, v1, … , vn-1, weights w0, w1, … , wn-1, and capacity C. For convenience, we assume
(1) Val[i, j] = Val[i – 1, j] for 0 ≤ j < wi
= max{ vi + Val[i – 1, j – wi ], Val[i – 1, j] } for wi ≤ j ≤ C ,
(2) B[i, j] = B[i – 1, j] if Val[i, j] = Val[i – 1, j],
= i otherwise
init. cond. B[0, j] = – 1 for j < w0, B[0, j] = 0 for w0 ≤ j ≤ C
Algorithms: Sequential, Parallel and Distributed, Second Edition 9-13
The straightforward algorithm based on this recurrence is to make n passes with i varying from
else
Val[0, j] ← V[0]
B[0, j] ← 0
endif
endfor
Remarks. For a fixed i, the values Val[i, j], j = 0, 1, …, C form an increasing multi-step
function, so the function is determined by the “corner” points where the jumps occur. A more
efficient algorithm than the straightforward algorithm above is obtained by maintaining the
corner points at each stage, and for stage i, and merging the corner points resulting from stage i
– 1, and the corner points resulting from shifting these latter corner points up by the amount
9.19 We consider the coin changing problem where the change amount C and all the
denominations d0 < d1 < ….< dn-1 are positive integers. For integers i,j, we let S[i,j] denote
the minimum number of coins of denominations d0, d1, …., di that make change j, 0 ≤ i ≤ n – 1,
(4) ND[i, j] = ND[i – 1, j] if S[i, j] = S[i – 1, j],
= k otherwise, where S[i, j] = S[i – 1, j – kdi] + k,
init. cond. ND[0, j] = 0 unless d0 divides j, in which case S[0,j] = j/d0 for j ≥ d0
The straightforward algorithm based on these recurrences is to make n passes with i varying
from 1 to n – 1. During each pass, j varies from di to C. The arrays S[0: n – 1, 0: C] and
endif
endfor
for i ← 1 to n – 1 do
for j ← D[i] to C do
S[i, j] ← S[i – 1, j]
9.20 We first note that solving the partition problem for a set of integers {b0, b1, …., bn-1} is
equivalent to solving the sum of subsets problem for {b0, b1, …., bn-1} and Sum = (b0 + b1 + ….
+ bn-1)/2. Thus, we will give a dynamic programming solution to the general sum of subsets
problem. Moreover, we will solve the optimization version, which asks for a subset of smallest
(6) SB[i, j] = SB[i – 1, j] if S[i, j] = S[i – 1, j],
= i otherwise,
init. cond. SB[0, j] = n + 1 unless b0 = Sum, in which case SB[0, Sum] = 0
The straightforward algorithm based on these recurrences is to make n passes with i varying
from 1 to n – 1. During each pass, j varies from bi to Sum. The arrays S[0: n – 1, 0: C] and