Homework 5

CS 482 - Summer 2007

Due: Friday, Jul 27

1.  
   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 2 in Chapter 7 of the text.
      
2.  
   1. [Ergonomic Architecture] Do Problem 6 in Chapter 7 of the text.
       
   2. [Hospitals and Patients] Do Problem 9 in Chapter 7 of the text.