Algorithm Design Techniques Fall 2009
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(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.