COSC1285/2123
COSC1285/2123 Algorithms and Analysis
Workshop 8
Dynamic Programming
Tutorial Exercises
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?
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.
8.2.1
a) Apply the bottom-up dynamic programming algorithm to the following instance of the knapsack
problem:
Knapsack capacity W = 5.
item weight value
1 2 $12
2 1 $10
3 3 $20
4 2 $15
b) Solve the instance using the memory function algorithm: which entries in the table can be ignored?
8.1.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. 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.
c©2021 RMIT University 1
COSC1285/2123
Practical Exercises
Objective
Students who complete this lab should:
• Be able to implement two versions of the dynamic programming knapsack algorithm.
• Be able to compare them empirically.
Knapsack Problem
The knapsack problem is defined as follows:
Problem 1. Given n items of known weights w1, . . . , wn and the values v1, . . . , vn and a knapsack of
capacity W , find the most valuable subset of the items that fit into the knapsack.
In this lab you will implement two dynamic programming algorithms.
The Algorithms
The lecture notes describes two dynamic programming algorithms for solving the knapsack problem. The
first algorithm solves the problem calculating solutions to all sub-problems of the original problem to
calculate a solution for the original problem (bottom up). The pseudo code for this algorithm is shown
below.
algorithm BuKnapsack (ksProblem)
// Solves the knapsack problem by dynamic programming (bottom up)
// input : An object ksProblem, representing an instance of a knapsack problem. This object holds an
array of items I[1 . . . n] (where each item x has a value x.v and weight x.w), knapsack capacity W and
number of items n.
// output : Table V [0 . . . n, 0 . . .W ] is created and filled, with the value of an optimal subset in V [n,W ]
and from which the items of an optimal subset can be found. The table is stored in the BuKnapsack
object.
1: n = ksProblem.n
2: W = ksProblem.W
3: for i← 0 to n do
4: V [i, 0]← 0
5: end for
6: for j ← 1 to W do
7: V [0, j]← 0
8: end for
9: for i← 1 to n do
10: for j ← 1 to W do
11: if j − I[i].w ≥ 0 then
12: V [i, j]← max(V [i− 1, j], I[i].v + V [i− 1, j − I[i].w])
13: else
14: V [i, j]← V [i− 1, j]
15: end if
16: end for
17: end for
You are to implement this algorithm in the BottomUpKnapsack class provided to you in the skeleton
code.
c©2021 RMIT University 2
COSC1285/2123
The second algorithm you are to implement solves the knapsack problem top-down, only calculating
necessary cells from the result table. The pseudo code for this algorithm is shown below.
algorithm TdKnapsack (ksProblem, i, j)
// Implement the memory function method (top-down) for the knapsack problem.
// input : An object ksProblem, representing an instance of a knapsack problem. This object holds an
array of items I[1 . . . n] (where each item x has a value x.v and weight x.w), knapsack capacity W and
number of items n. A non-negative integer i indicating the number of the first items being considered
and a non-negative integer j indicating the knapsack capacity.
// output : The value of an optimal, feasible subset of the first i items.
// Note: Requires table V [0 . . . n, 0 . . .W ] initialized with −1s, except for row 0 and column 0 being all
0s.
1: if V [i, j] < 0 then
2: if j < I[i].w then
3: x← TdKnapsack(i− 1, j)
4: else
5: x← max( TdKnapsack(i− 1, j), I[i].v+ TdKnapsack(i− 1, j − I[i].w))
6: end if
7: V [i, j]← x
8: end if
9: return V [i, j]
You are to implement this algorithm in the TopDownKnapsack class provided to you in the skeleton
code.
file description
KnapsackDemo.java code to generate ranodm knapsack problem instances then call the two
implementations of knapsack algorithms. No need to modify this file.
Knapsack.java implementation of a knapsack instance. Examine class to see how to get an
instance information. No need to modify this file.
KnapsackAlgor.java abstract class implementing some common functionality for the knapsack
algorithms. No need to modify this file.
BottomUpKnapsack.java implement bottom up knapsack. Complete the implementation.
TopDownKnapsack.java implement top down knapsack. Complete the implementation.
Compile the code using the following command:
javac *.java
To run the demo:
java KnapsackDemo
c©2021 RMIT University 3
COSC1285/2123
A sample call the program should produce the following output:
˜> javac ∗ . java
˜> java KnapsackDemo 8 20 true
item | weight | value
1 | 6 | 11
2 | 1 | 1
3 | 6 | 13
4 | 8 | 18
5 | 2 | 3
6 | 3 | 14
7 | 6 | 18
8 | 2 | 5
Bottom up Knapsack time taken = 4.96437E−4
Maximum value = 56
Bottom up Knapsack time taken = 2.76175E−4
Maximum value = 56
Make sure both algorithms return the same result for a given knapsack problem instance.
Questions
After implementing the two algorithms try answering the following questions:
• What is the maximum problem size you can solve?
• Which algorithm is faster?
c©2021 RMIT University 4