Description
1. Minimum cut of a graph is the minimum over all pairs of vertices of the minimum cut for the
pair. Let m be the number of edges and n be the number of vertices, give an O(m2n) algorithm
that finds the minimum cut of a directed strongly connected unweighted graph. (Hint: do just n
max-flows and argue that the max-flow algorithm we have seen in class that works for integer
capacities will cost at most O(m2
) time).
2. We have learned that the minimum number of edges that need to be removed to disconnect a
pair s and t of vertices equals the maximum number of edge disjoint paths between s and t.
Can we make a similar statement about vertices? Specifically, is the following statement true or
false: the minimum number of vertices that need to be removed to disconnect s and t equals the
maximum number of vertex disjoint paths between s and t. Either prove the correctness or give
a counter-example disproving the statement.
3. Take a standard deck of cards, and deal them out into 13 piles of 4 cards each. Show that it is
always possible to select exactly 1 card from each pile, such that the 13 selected cards contain
exactly one card of each rank (Ace, 2, 3, . . . , Queen, King).
4. UCLA hires you to write an algorithm to schedule their final exams. Each quarter, UCLA offers
n different classes. There are r different rooms on campus and t different time slots in which
exams can be offered. You are given two arrays E[1..n] and S[1..r], where E[i] is the number of
students enrolled in the i
th class, and S[ j] is the number of seats in the j
th room. At most one
final exam can be held in each room during each time slot. Class i can hold its final exam in room
j only if E[i] < S[ j]. Describe and analyze an efficient algorithm to assign a room and a time slot
to each class (or report correctly that no such assignment is possible). Formulate the problem as
max-flow problem and argue the correctness of your construction.
Æ Homework assignments are STRICTLY due on the exact time indicated. Please submit a hard copy
of your homework solution with your Name,Bruin ID, Discussion Number, clearly indicated on
the first page. If your homework consists of multiple pages, please staple them together. Email
attachments or other electronic delivery methods are not acceptable.
Æ We recommend to use LATEX, LYX or other word processing software for submitting the homework.
This is not a requirement but it helps us to grade the homework and give feedback. For grading,
we will take into account both the correctness and the clarity. Your answer are supposed to be in
a simple and understandable manner. Sloppy answers are expected to receiver fewer points.
Æ Unless specified, you should justify your algorithm with proof of correctness and time complexity.
1
