Algorithm Design Techniques      Winter 2008

 COMP-360              Assignment 2           Due: Beginning of class, Tues Feb 5


Late assignments  -10% per day, including weekends.
Please give late assignments to Anil (T.A) in McConnell 337
If you work closely with someone else, indicate the person's name(s) on your homework.
The final write-up of each assignment must, however, be your own work.




1. (Bellman-Ford). Consider the Bellman-Ford algorithm given on p. 294.
You are given a directed graph G, destination vertex t, integer k, and edge weights that may be negative.
You are told that for each vertex v all simple paths (ie. no repeated vertex) from v to t have at most k edges.

(a) Suppose G has  no negative cycle. If the algorithm is terminated after the iteration  i=k , will M contain all shortest paths to t?
(b) Suppose G may have a negative cycle on a path to t. Can this be detected and the algorithm terminated after the iteration when i=k+1?

Give a proof or counterexample in each case above.


2. (DP) Text, P. 316, problem 5.

3. (DP) Text, P.320, problem 9.
______________________________________________________________________________________________________________________________

4. (Network Flow) Text, P 418, problem 8.

5. (Network Flow) Text, P 421, problem 15.
Solve the problem for n=5, with nights labelled 1,2,...,5 and S_1={2,3}, S_2={4,5}, S_3={1,2}, S_4={1,3}, S_5={1,4,5}.
Draw the graph, the corresponding network, and show a maximum flow and maximum matching.
Also illustrate part (b) of problem 15 on this example, by initially having two people assigned to night 5.