Advanced Data Structures

Fall 2003

[ CIS 410/510 | CIS | UO | News ]

Assignment 4

Due Wednesday Oct. 29

  1. What is the (tight) amortized complexity of ADT Partition implemented by directed trees (pointers to the parent) with Union by rank and Find with path compression, when all Finds occur after all Unions?

  2. What is the (tight) amortized complexity of ADT Partition implemented by directed trees (pointers to the parent) with arbitrary Union and Find with path compression? (see CLR 21.3-3)

  3. What is the difference between the complexity analysis of the implementation of ADT Partition as presented in RET and that in CLR? Specifically, would (or would not) the analysis of CLR be sufficient for RET result on MWST algorithm?

  4. (Problem 21-1 from CLRS) Provide an invariant argument for the correctness of the Off-Line-Minimum algorithm on page 519 (couch the for loop as a while loop with condition i<n+1). Give a tight bound on the worst-case running time of the algorithm implemented with state-of-art ADT Partition.

  5. (Extra: Problem 21-2 from CLRS) Answer questions b-e, or at least describe (in your own words and with an example) the idea of the algorithm for efficient depth determination.