CS 410 Fall 99
Homework 2
Due Thursday, September 23

Reading

Written Exercises

1. Suppose you are given a binary search tree, possibly unbalanced, and want to rebalance it. Consider the following recursive algorithm:

      (i) Find the location of the median element.

      (ii) Rotate it up to the root.

      (iii) Apply the algorithm recursively to the two subtrees.

   (a) Prove that the resulting tree is balanced; that is, show that it has paths of length O(log n).

   (b) Argue that the worst-case running time of this algorithm is Theta(n log n).

   (c) Can you come up with a better algorithm? (Hint. O(n) is possible.)

2. Suppose we had a lazy-merge binomial heap consisting of a list of n B(0) trees, each containing a single data element, and suppose we wanted to consolidate the heap as in deletemin. How long does this take? Do not give an amortized bound, but the actual time taken by the operation. (Hint. Think of starting from 0 and incrementing n times using binary addition.)
3. Describe a data structure that admits the same operations as Fibonacci heaps with the same amortized running times, but also allow findmax and deletemax in addition to findmin and deletemin. The amortized times of the max operations should be the same as for the corresponding min operations. (Hint. Don't think too hard about this one, the solution is relatively straightforward...)
4. Give an O(n) algorithm for augmenting a binary tree with extra information at the nodes so that subsequent queries of the following form can be answered in constant time: given two nodes b and c in the tree, is b a descendant of c? (Hint. Think of the way we represented a heap in an array such that the descendants of a node at index i were found at locations 2i and 2i+1. Now think of these indices as Boolean bit strings. You may assume constant-time word-length Boolean operations on bit strings representing integers.)