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

The goal is to assign papers to reviewers so that

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.