School of Computing and Information Systems
COMP90038 Algorithms and Complexity Tutorial Week 11
Sample Answers
The exercises
74. Use the dynamic-programming algorithm developed in Lecture 18 to solve this instance of
the coin-row problem: 20, 50, 20, 5, 10, 20, 5.
Answer: We build the table S of optimal values as follows:
i : 0 1 2 3 4 5 6 7
C[i] : − 20 50 20 5 10 20 5
S[i] : 0 20 50 50 55 60 75 75
The optimal selection uses the coins at indices 2, 4, and 6.
75. In Week 12 we will meet the concept of problem reduction. This question prepares you for
that. First, when we talk about the length of a path in an un-weighted directed acyclic graph
(dag), we mean the number of edges in the path. (You could also consider the un-weighted
graph weighted, will all edges having weight 1.)
Show how to reduce the coin-row problem to the problem of finding a longest path in a dag.
That is, give an algorithm that transforms any coin-row instance into a longest-path-in-dag
instance in such as way that a solution to the latter provides a solution to the former.
Hint: If there are n coins, use n+ 1 nodes; let an edge with weight i correspond to picking a
coin with value i.
Answer: Assume we have n coins c1, . . . , cn. We generate a weighted dag with n+ 1 nodes
C0, C1, . . . , Cn. The dag has edges as follows:
• n− 1 edges (C0, Cn), (C1, Cn), . . . , (Cn−2, Cn), each with weight cn.
• n− 2 edges (C0, Cn−1), (C1, Cn−1), . . . , (Cn−3, Cn−1), each with weight cn−1.
• and so on, down to two edges (C0, C3) and (C1, C3), each with weight c3.
• one edge (C0, C2) with weight c2, and
• one edge (C0, C1) with weight c1.
Any path in the generated dag corresponds to a legal selection of coins, and the sum of the
weights along a given path is exactly the sum of the coins chosen.
76. Consider the problem of finding the length of a “longest” path in a weighted, not necessarily
connected, dag. We assume that all weights are positive, and that a “longest” path is a path
whose edge weights add up to the maximal possible value. For example, for the following
graph, the longest path is of length 15:
a
b
c
d
e
f g h
3
1
4
6
3
2
4
1
9
Use a dynamic programming approach to the problem of finding longest path in a weighted
dag.
Answer: This is easy if we process the nodes in topologically sorted order. For each node t
we want to find its longest distance from a source, and to store these distances in an array
L. That is, for each t we want to calculate
max({0} ∪ {L[u] + weight[u, t] | (u, t) ∈ E})
So:
T ← TopSort(⟨V,E⟩) — List of nodes sorted topologically
for each t ∈ T (in topological order) do
L[t]← 0
for each u ∈ V do
if (u, t) ∈ E then
if L[u] + weight[u, t] > L[t] then
L[t]← L[u] + weight[u, t]
max ← 0
for each u ∈ V do
if L[u] > max then
max ← L[u]
return max
For the sample graph, DFS-based topsort yields the sequence g, h, a, c, b, d, e, f . The
“longest path” table L gets filled as follows:
t : a b c d e f g h
L[t] : 0
9
0
1
5
11
13
15
77. Design a dynamic programming algorithm for the version of the knapsack problem in which
there are unlimited numbers of copies of each item. That is, we are given items I1, . . . , In
that have values v1, . . . , vn and weights w1, . . . , wn as usual, but each item Ii can be selected
several times. Hint: This actually makes the knapsack problem a bit easier, as there is only
one parameter (namely the remaining capacity w) in the recurrence relation.
Answer: Assume the items I1, . . . , In have values v1, . . . , vn and weights w1, . . . , wn. Let
V (w) denote the optimal value we can achieve given capacity w. With capacity w we are in a
position to select any item Ii which weighs no more than w. And if we pick item Ii then the
best value we can achieve is vi + V (w − wi). As we want to maximise the value for capacity
w, we have the recurrence
V (w) = max{vi + V (w − wi) | 1 ≤ i ≤ n ∧ wi ≤ w}
That leads to this table-filling approach:
for w ← 1 to W do
V [w]← max({0} ∪ {vi + V (w − wi) | 1 ≤ i ≤ n ∧ wi ≤ w})
return V [W ]
As an example, consider the case W = 10, and three items I1, I2, and I3, with weights 4, 5
and 3, respectively, and values 11, 12, and 7, respectively. The table V is filled from left to
right, as follows:
w : 1 2 3 4 5 6 7 8 9 10
V [w] : 0 0 7 11 12 14 18 22 23 25
Hence the optimal bag is [I1, I3, I3] for a total value of 25.
78. Work through Warshall’s algorithm to find the transitive closure of the binary relation given
by this table (or directed graph):
a b c d
a 0 0 1 1
b 0 0 1 0
c 1 0 0 0
d 0 0 0 0
dacb
Answer: We run down the columns from left to right, stopping when we meet a 1. This first
happens when we are in row 3, column 1. At that point, ‘or’ row 1 onto row 3 (and so on):
a b c d
a 0 0 1 1
b 0 0 1 0
c 1 0 1 1
d 0 0 0 0
⇒
a b c d
a 1 0 1 1
b 0 0 1 0
c 1 0 1 1
d 0 0 0 0
⇒
a b c d
a 1 0 1 1
b 1 0 1 1
c 1 0 1 1
d 0 0 0 0