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