### 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.