Plan
The exam is not far away, so keep up with tutorials; as always, try tackling the problems before the tute.
The exercises
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, with 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.
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:
Use a dynamic programming approach to the problem of finding longest path in a weighted dag.
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.
78. Work through Warshall’s algorithm to find the transitive closure of the binary relation given by this table (or directed graph):
0 0 1 1
0 0 1 0
1 0 0 0
0 0 0 0
a b c d a b c d
