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.