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.