Advanced Data Structures

Fall 2003

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

Assignment 3

Due Monday Oct. 20

  1. Provide credit invariant argument of amortized complexity of Fibonacci Queues.

  2. (Ex. 20.2-4 from CLRS) A McGeeHeap has the same structure as a Fibonacci heap and supports the same mergeable-heap operations. The implementations of the operations are the same as for Fibonacci heaps, except that insertion and union perform consolidation as their last step. What are the worst-case running times of operations on McGeeHeaps? How novel is the data structure?

  3. (Ex. 20.2-5 from CLRS) Argue that when the only operations on keys are comparing two keys, not all of mergeable-heap operation can run in O(1) amortized time.

  4. Give an implementation of ADT Partition with
    1. O(1) Union and O(log n) Find;
    2. O(1) Find and O(log n) Union.

  5. (Where is Waldo?) Section 3.4 of RET gives a solution to an efficient implementation of the operation addToKeys: PQ x Prio -> PQ. Find the "other use of storing differences" mentioned in the section.