# Homework 4

## CS 482 - Spring 2007

### Due: Wednesday, March 7

**Reminder: **Please include your Cornell NetID on your each part of your
homework. We plan to start taking off points for those who neglect to include
their NetID.

### Part A

- [n Consecutive Finds] For the union/find data structure on n elements using path compression,
prove that any sequence of n consecutive Find operations takes time O(n).
[Note that the sequence of n Find operations takes place
*after* an
unspecified number of Unions and/or Finds.]

- [Flow Example] Do Problem 3 in Chapter 7 of the text.

### Part B

[Blood Supply] Do Problem 8 in Chapter 7 of the text.

### Part C

[Program Committee] Papers for a conference are usually selected by a *program
committee*. A typical goal is to have each paper reviewed by three
committee members, but some reviewer/paper combinations are disallowed (because,
for instance, the paper is written by the reviewer's student). Suppose we
are given

- n conference papers,
- k committee members, and
- m pairs of the form (c, p) where c is a committee member
*allowed to*
review paper p.

The goal is to assign papers to reviewers so that

- each paper is reviewed by exactly 3 committee members,
- each committee member reviews exactly 15 papers, and
- each committee member reviews only allowed papers.

Describe a polynomial time algorithm to determine if there is a valid way to assign papers to committee members and to report such an assignment if it
exists. You can assume that 3n=15k; in other words, assume that there are
exactly enough reviewers to produce the right number of reviews for each paper.