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

1. [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.]
    
2. [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.