Description

Hand in your solutions electronically using CMS. Each solution should be submitted

as a separate file. Collaboration is encouraged while solving the problems, but:

1. list the names of those with whom you collaborated;

2. you must write up the solutions in your own words.

Remember that when a problem asks you to design an algorithm, you must also

prove the algorithms correctness and analyze its running time. The running time

must be bounded by a polynomial function of the input size.

(1) (10 points) Implement the Ford-Fulkerson algorithm in java using the environment provided

— use the framework code FrameworkFlow.java we provide on CMS, to read the input and

write the output in a specific form (this makes it easy for us to test your algorithm). The only

thing you need to implement is the algorithm, and you are restricted to implement this between

the lines //YOUR CODE STARTS HERE and //YOUR CODE ENDS HERE. This is to make sure you can

only use classes from java.util (imported at the start of the file), and the nested class Edge.

Your implementation should run in O(Cm) time as discussed in lecture.

Warning: Be aware that the running time of calling a method of a built-in Java class

is usually not constant time, and take this into account when you think about the

overall running time of your code. For instance, if you use a LinkedList, and use the

indexOf method, this will take time linear in the number of elements in the list.

You can test your code with the test cases provided on CMS. FrameworkFlow.java takes two

command line arguments, the first is the name of the input file, and the second is the name of

the output file.

The format of the input file is the following:

•  The first three lines contain one number: n, the number of nodes, s, the node number of

the source, and t, the node number of the sink, respectively.

•  The next n lines consist of the adjacency lists of the nodes and the capacity of the corre-

spending arcs. To be precise: line 4 + i corresponds to node i (the nodes are numbered 0

to n − 1), and lists a node j, and directly next to it the capacity of arc (i, j) for all nodes

j reachable from i (for instance, if line 4 is 1 5 6 8, then nodes 1 and 6 can be reached

from node 0, and the capacity of arc (0, 1) is 5, the capacity of arc (0, 6) is 8).

The output file is similar, except that the capacities are replaced by the flow on the arc.

The code reads in the input and stores the adjacency list (as objects of the class Edge) of node

i as entry i of the array adjacencyList, i.e. adjacencyList[i][k] is the (k + 1)st edge leaving

node i.

The nested class Edge, with fields head node, tail node, capacity, flow, original edge and

isForwardEdge is given for your convenience, and you are free to use it or ignore (parts of) it.

Your code should assign values that correspond to a Maximum Flow to the flow field of the

edges.

We use Java 8 for compiling and testing your program.

(2) (10 points) At Ford-Fulkerson University (motto: “I would find a graph whose maximum flow

value is different from its minimum cut capacity, but there is no such graph.”) there are many

committees that need to be staffed with professors. The university has n professors organized

into departments; each professor belongs to only one department. There are m committees, and

the following constraints must be satisfied when staffing the committees.

1. The required number of professors on committee k is specified by a positive integer rk.

2. No professor is allowed to serve on more than c committees.

3. No committee is allowed to have more than one professor from the same department.

4. For each professor j, there is a list Lj of the committees on which he or she is qualified

to serve. Professor j is not allowed to serve on committee k unless k ∈ Lj

. Professor j

belongs to department dj

.

Design a polynomial-time algorithm to determine whether it is possible to staff each committee

without violating any of the constraints listed above. If it is possible to staff the committees,

your algorithm should output an assignment of professors to committees that satisfy all of

the constraints. The input to the problem is specified by the numbers n, m, r1, . . . , rm, the

departments of the professors d1, . . . , dn, and the lists L1, . . . , Ln.

(3) (10 points) In a flow network G = (V, E,~c, s, t), let us define an edge e to be useless if the

relation f(e) = 0 is satisfied by every maximum flow f. Design a polynomial-time algorithm

that takes a flow network G and a maximum flow  ̄f on this network, and outputs a list of all of

its useless edges.

For full credit, your algorithm’s running time should be O(m2

) or faster.