COSC1285/2123
COSC1285/2123 Algorithms and Analysis
Tutorial 8
Dynamic Programming
Objective
Students who complete this tutorial should:
• Be familiar with the concept of dynamic programming.
Questions
8.1.1 What does dynamic programming have in common with divide-and-conquer? What is a principal
difference between the two techniques?
Answer:
a) Both techniques are based on dividing a problem’s instance into smaller instances of the same
problem.
b) Typically, divide-and-conquer divides an instance into smaller instances with no intersection whereas
dynamic programming deals with problems in which smaller instances overlap. Consequently,
divide-and-conquer algorithms do not explicitly store solutions to smaller instances and dynamic
programming algorithms do.
Q2. Consider the two strings “perturb” and “superb”. Compute the edit distance between the two
strings, assume an edit cost of 1 for any character differences. Show the dynamic programming table and
the traceback. Circle the elements in the table when showing the traceback. If there is more than one
possible traceback, just show one of them.
Answer: See Table 1.
– p e r t u r b
– 0 1 2 3 4 5 6 7
s 1 1 2 3 4 5 6 7
u 2 2 2 3 4 4 5 6
p 3 2 3 3 4 5 5 6
e 4 3 2 3 4 5 6 6
r 5 4 3 2 3 4 5 6
b 6 5 4 3 3 4 5 5
Table 1: Answer to 6.
8.2.1
a) Apply the bottom-up dynamic programming algorithm to the following instance of the knapsack
problem:
Knapsack capacity W = 5.
b) Solve the problem using a top-down approach with a memory function.
Answer:
a) The maximal value of a feasible subset is V [4, 5] = 37. The optimal subset is item 1, item 2, item
4:
c©2021 RMIT University 1
COSC1285/2123
item weight value
1 2 $12
2 1 $10
3 3 $20
4 2 $15
V [i, j] j = 0 1 2 3 4 5
i = 0 0 0 0 0 0 0
1 0 0 12 12 12 12
2 0 10 12 22 22 22
3 0 10 12 22 30 32
4 0 10 15 25 30 37
b) Solving by using the memory function algorithm.
V [i, j] j = 0 1 2 3 4 5
i = 0 0 0 0 0 0 0
1 0 0 12 12 12 12
2 0 – 12 22 – 22
3 0 – – 22 – 32
4 0 – – – – 37
8.1.7 Shortest path counting (Time permiting) A chess rook can move horizontally or vertically to any
square in the same row or in the same column of a chessboard. Find the number of shortest paths by
which a rook can move from one corner of a chessboard to the diagonally opposite corner by a dynamic
programming algorithm.
Answer: 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. Let P (i, j) be the number
of the rook’s shortest paths from square (1, 1) to square ( i, j ) in the ith row and the jth column, where
1 ≤ i, j ≤ 8. Any such path will be composed of vertical and horizontal moves directed toward the goal.
Obviously, P (i, 1) = P (1, j) = 1 for any 1 ≤ i, j ≤ 8. In general, any shortest path to square ( i, j ) will
be reached either from square ( i, j – 1) or from square ( i – 1, j ) square. Hence, we have the following
recurrence:
P (i, j) = P (i, j − 1) + P (i− 1, j) for 1 < i, j ≤ 8, P (i, 1) = P (1, j) = 1, for 1 ≤ i, j ≤ 8 Using this recurrence, we can compute the values of P (i, j) for each square ( i, j ) 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: c©2021 RMIT University 2 COSC1285/2123 c©2021 RMIT University 3