Algorithm Design Techniques

COMP-360 Assignment 2 Due: 5pm Friday October 7, 2005

Please leave your assingment in the box marked COMP360, 1st floor McConnell.
Late assignments -10% per day, including weekends. Hand in late assignments to the T.A.
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.

Problems from handout given in class September 29

1. Problem 5.

2. Problem 8. Draw the network and solve by the augmenting path method. Show the augmenting flow for each iteration.

3. Problem 11.

4. Problem 16. Show how to formulate this problem as a network flow problem.
Construct two small non-trivial examples with say k=m=3 and n=5.
One for which a solution is possible and one for which it is not.
Give a certificate in each case based on the max flow/min cut theorem.