Algorithm Design Techniques     Fall 2009

COMP-360              Assignment 3           Due: Friday Oct 16, 5pm

No Late Assignments!
Please leave assignments in the drop off box, Trottier 3rd floor.
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. Consider the network flow problem with the following edge capacities, c(u,v) for edge (u,v):
c(s,2)=2, c(s,3)=13, c(2,5)=12,  c(2,4)=10, c(3,4)=5,  c(3,7)=6, c(4,5)=1,
c(4,6)=1, c(6,5)=2, c(6,7)=3, c(5,t)=6, c(7,t)=2

(a) Draw the network.
(b) Run the Ford-Fulkerson algorithm to find the maximum flow. Show each residual graph.
(c) Show the minimum cut.

2. Consider assigning interns to hospitals in the following situation. There are n interns and m hospitals.
Hospital i has a requirement for d(i) interns, i=1,2,3,...,m.
A compatability graph is set up with edges (u,v) if intern u is compatible with hospital v.
Suppose the graph has the following two properties, for some integer k
-Each intern is compatible with exactly k hospitals.
-Hospital i is compatible with exactly k*d(i) interns.

(a) Prove that it is always possible to assign each intern to a compatible hospital (use network flows).
(b) Illustrate for the case n=7, m=3, d(1)=3, d(2)=2, d(3)=2 and k=2.

3. P. 423, Problem 17.

4. P. 427 Problem 21. For part (a) you need to give a proof (ie. certificate of some kind) that there is no test set of size n.
Choose n to be at least 5.
Also give a tight bound on the running time in terms of n.