Homework 3

1. Consider a perfect tree of height h, where every non-leaf node has 3 children. (Therefore, each of the 3^h leaves is at distance h from the root.) Every leaf has a boolean value associated with it - either 0 or 1. Every internal node gets the boolean value assigned to the majority of its children. Given the values assigned to the leaves, we want to find an algorithm that computes the value (0 or 1) of the root.

   It is not hard to find a (deterministic) algorithm that looks at every leaf and correctly determines the value of the root, but this takes O(3^h) time. Describe and analyze a randomized algorithm that, on average, looks at asymptotically fewer leaves. That is, the expected number of leaves your algorithm examines should be o(3^h). (That is little-Oh of 3^h.)

2. A binary heap is a binary tree where each node contains a priority, and such that the priority of a node is less than the priority of its parent. (We do not assume any balancing condition, any shape of tree is allowed, and a node can have zero, one, or two children.) The priority of a heap is defined as the priority of its root.

   We define a new operation Fuse for two (binary) heaps, that builds a new heap H out of two given heaps A and B as follows.

   Let A be the heap with higher priority, and let a be the root of A. (And so a has to be the root of the new heap H.) Let A' and A" be the left and right subtree of a.

   We flip a coin that comes up either left or right, with equal probability.

   If the coin comes up "left", then we build H as follows: The root is a, the left subtree is A', and the right subtree is built recursively by fusing A" with B.

   If the coin comes up "right", then we build H as follows: The root is a, the right subtree is A", and the left subtree is built recursively by fusing A' with B.

   The base case is when one heap becomes empty, then the result of fusing is the other heap.

   1. Given two heaps A with n elements and B with m elements, what is the expected running time of Fuse(A,B)?
   2. Describe how to perform each of the following operations using only Fuse operations, and give the running time of each:
      • DeleteMax(H), which deletes the element with greatest priority.
      • Insert(H, x), which inserts the element x into the heap H.
      • Delete(H, x), given a pointer to element x in heap H, returns the heap with x deleted.
3. [Extra Credit]: In last week's homework, we found an O(n) algorithm RandomSelect for selecting the kth smallest element, but the constant hidden in the Big-Oh notation is somewhat large. It is easy to find the smallest element using at most n comparisons; we would like to be able to extend this to larger k.

   Can you find a randomized algorithm that uses n+O(k log k log n) expected comparisons? (Note that there is no constant multiplying the n.)

   Hint: While scanning through a random permutation of n elements, how many times does the smallest element seen so far change? How many times does the kth smallest element so far change?