This file contains the exercises, hints, and solutions for Chapter 8 of the
book ”Introduction to the Design and Analysis of Algorithms,” 3rd edition, by
Exercises 8.1
1. What does dynamic programming have in common with divide-and-conquer?
What is a principal difference between them?
2. Solve the instance 5, 1, 2, 10, 6 of the coin-row problem.
5. How would you modify the dynamic programming algorithm for the coin-
collecting problem if some cells on the board are inaccessible for the robot?
Apply your algorithm to the board below, where the inaccessible cells are
shown by X’s. How many optimal paths are there for this board?
7. Shortest-path counting A chess rook can move horizontally or vertically
to any square in the same row or in the same column of a chessboard.
8. Minimum-sum descent Some positive integers are arranged in an equi-
lateral triangle with numbers in its base like the one shown in the figure
9. Binomial coefficient Design an efficient algorithm for computing the bi-
nomial coefficient ( )that uses no multiplications. What are the time
and space efficiencies of your algorithm?
10. Longest path in a dag a. Design an efficient algorithm for finding the
length of a longest path in a dag. (This problem is important both as
11. IMaximum square submatrix Given an ×boolean matrix find its
largest square submatrix whose elements are all zeros. Design a dynamic
12. IWorld Series odds Consider two teams, Aand B, playing a series of
games until one of the teams wins games. Assume that the probabil-
ity of winning a game is the same for each game and equal to and
the probability of losing a game is =1− (Hence, there are no
Hints to Exercises 8.1
2. Use the table generated by the dynamic programming algorithm in solving
the problem’s instance in Example 1 in the section.
3. a. The analysis is similar to that of the top-down recursive computation
4. Apply the dynamic programming algorithm to the instance given as it is
done in Example 2 of the section. Note that there are two optimal coin
combinations here.
5. Adjust formula (8.5) for inadmissible cells and their immediate neighbors.
9. Use a well-known formula from elementary combinatorics relating ( )
to smaller binomial coefficients.
10. a. Topologically sort the dag’s vertices first.
b. Create a dag with +1 vertices: one vertex to start and the oth-
ers to represent the coins given.
c. Your pseudocode should be guided by the recurrence set up in part
4
(a). The efficiency answers follow immediately from the table’s size and
the time spent on computing each of its entries.
5
Solutions to Exercises 8.1
1. Both techniques solve a problem by dividing it into several subproblems.
2. The application of the dynamic programming algorithm to the input 5, 1,
2, 10, 6, 2 in section 8.1 yielded the following table:
3. a. The time efficiency analysis of the algorithm in question is identical to
that of the top-down computation of the th Fibonacci number in Section
2.5: see recurrence (2.11) for the number of additions made by both al-
gorithms. Hence, the time efficiency class is Θ()where =(1+
√5)2
b. If an exhaustive search algorithm generates all the subsets of the coin
row given before checking which of them don’t include adjacent coins, the
number of the subsets will be equal 2which answers the question. But
4. The application of the dynamic programming algorithm to the instance
6
given yields the following table
[0] = 0 0123456789
0
01212
[5] = min{[5 −1][5 −3][5 −5]}+1=2 0123456789
012121
[6] = min{[6 −1][6 −3][6 −5]}+1=2 0123456789
0121212
Application of Algorithm MinCoinChange to amount =9and coin denominations 1, 3, and 5
The minimum number of coins obtained is (9) = 3There are two
optimal coin sets: {135}and {333}
5. Formula (8.5) used for computing the largest number of coins that can be
brought to a cell needs to be adjusted as follows. If a cell is inadmissible
or has no admissible neighbors above or to the left of it, it is marked as
inadmissible (if it hasn’t been already marked as such) and no value is
right corner is 4; there are 12 different paths for the robot to do this.
.
6. Let ()be the maximum price for a given rod of length We have the
following recurrence for its values:
8
7. a. With no loss of generality, we can assume that the rook is initially
located in the lower left corner of a chessboard, whose rows and columns
are numbered from 1 to 8 bottom up and left to right, respectively. Let
( )be the number of the rook’s shortest paths from square (1,1) to
Using this recurrence, we can compute the values of ( )for each square
()of the board. This can be done either row by row, or column by
column, or diagonal by diagonal. (One can also take advantage of the
board’s symmetry to make the computations only for the squares either
on and above or on and below the board’s main diagonal.) The results
are given in the diagram below:
1 8 36 120 330 792 1716 3432
17161 7 28 84 210 462 924
9
b. Any shortest path from square (1,1) to square (8,8) can be thought
of as 14 consecutive moves to adjacent squares, seven of which being up
while the other seven being to the right. For example, the shortest path
8. Using the standard dynamic programming technique, compute the mini-
mum sum along a descending path from the apex to each number in the
triangle. Start with the apex, for which this sum is obviously equal to
the number itself. Then compute the sums moving top down and, say,
left to right across the triangle’s rows as follows. For any number that is
9. The recurrence underlying the algorithm in question is
( )=(−1−1) + (−1)for 0
( 0) = ( )=1
Here is pseudocode of the dynamic programming algorithm based on these
formulas.
The algorithm computes all the binomial coefficients ( )for 0≤≤
and 0≤≤min( )which fill the triangular table with +1 rows followed
by a rectangular table with −rows and +1 columns. One addition is
made to compute each binomial coefficient, except those columns 0 and in the
triangular table and those in column 0 in the rectangular table. Therefore we
11
So, we can obtain an upper bound by eliminating the negative terms:
Hence ( )∈Θ()which indicates the time efficiency class of the algo-
rithm.
The space efficiency of the above algorithm is also Θ()since the computed
binomial coefficients occupy their own memory cells in the rectangular table with
+1 rows and +1 columns. Considering only the memory cells actually used
by the algorithm still yields the same asymptotic class:
Algorithm Binomial2 ( )
//Computes ( )by the dynamic programming algorithm
//with a one-dimensional table
//Input: A pair of nonnegative integers ≥≥0
//Output: The value of ( )
10. After topological sorting of the digraph’s vertices, the following formula
for the length of the longest path to vertex is all but obvious:
=max
()∈{+( )}
a. Algorithm DagLongestPath()
b. The dag in question will have +1 vertices, placed for convenience in
a row mimicking the coin row: vertex 0 for the start and the other vertices
11. We will assume that the rows and columns of a given matrix are num-
bered from 1 to and from 1 to , respectively. Let ( )be the order of
the largest all-zero submatrix of a given matrix with its low right corner
at ( )If =1( )=0accordingtothedefinition of ( )The
nontrivial case is that of =0In this case, one can prove that
13
Considerthecaseof =0(−1)=and ( −1) = where 6=
Without loss of generality, we assume that
123456
1001000
0123456
00000000
10110111
12. a. Let ( )be the probability of winning the series if needs more
games to win the series and needs more games to win the series. If
team wins the game, which happens with probability ,will need
−1more wins to win the series while will still need wins. If team
b. Here is the dynamic programming table in question, with its entries
rounded-offto two decimal places. (It can be filled either row-by-row, or
column-by-column, or diagonal-by-diagonal.)
\01234
01111
100.400.640.780.87
14
Thus, [44] ≈029
c. Algorithm WorldSeries( )
//Computes the odds of winning a series of games
//Input: A number of wins needed to win the series
// and probability of one particular team winning a game
15
Exercises 8.2
1. a. Apply the bottom-up dynamic programming algorithm to the following
instance of the knapsack problem:
item weight value
13 $25
b. How many different optimal subsets does the instance of part (a) have?
2. a. Write pseudocode of the bottom-up dynamic programming algorithm
for the knapsack problem.
3. For the bottom-up dynamic programming algorithm for the knapsack
problem, prove that
4. a. True or false: A sequence of values in a row of the dynamic program-
ming table for the knapsack problem is always nondecreasing.
b. True or false: A sequence of values in a column of the dynamic pro-
gramming table for the knapsack problem is always nondecreasing?
5. Design a dynamic programming algorithm for the version of the knapsack
6. Apply the memory function method to the instance of the knapsack prob-
lem given in Problem 1. Indicate the entries of the dynamic programming
7. Prove that the efficiency class of the memory function algorithm for the
8. Give two reasons why the memory function approach is unattractive for
the problem of computing a binomial coefficient.
17
Hints to Exercises 8.2
1. a. Use formulas (8.6)—(8.7) to fill in the appropriate table, as is done for
another instance of the problem in the section.
2. a. Write pseudocode to fill the table in Fig. 8.4 (say, row by row) by using
formulas (8.6)—(8.7).
b. An algorithm for identifying an optimal subset is outlined in the section
via an example.
5. The problem is similar to one of the problems discussed in Section 8.1.
6. Trace the calls of the function MemoryKnapsack ( )on the instance in
question. (An application to another instance can be found in the section.)
Solutions to Exercises 8.2
1. a. capacity
0123456
00000000
1=3
1=25 10 0 0 25252525
2. a. Algorithm DPKnapsack([1][1])
//Solves the knapsack problem by dynamic programming (bottom up)
//Input: Arrays [1]and [1]of weights and values of items,
// knapsack capacity
//Output: The table [0 0 ]that contains the value of an optimal
b. Algorithm OptimalKnapsack([1][1][0 0 ])
//Finds the items composing an optimal solution to the knapsack problem
19
3. The algorithm fills a table with +1rows and +1columns, spending
Θ(1) time to fill one cell (either by applying (8.6) or (8.7). Hence, its
time efficiency and its space efficiency are in Θ( )
4. Both assertions are true:
a. ( −1) ≤( )for 1≤≤is true because it simply means that
the maximal value of a subset that fits into a knapsack of capacity −1
5. Here, the recurrence underlying the dynamic-programming algorithm is
6. In the table below, the cells marked by a minus are the ones for which no
entry is computed for the instance in question; the only nontrivial entry
that is retrieved without recomputation is (21).
20