hw4-soln CS 161|ALL YOU NEED

CS161 Homework 4 Due: 15 May 2015 Submit on Scoryst Handed out: 8 May 2015 Instructions: Please answer the following questions to the best of your ability. If you are asked to show your work, please include relevant calculations for deriving your answer. If you are asked to explain your answer, give a short (∼ 1 sentence) intuitive description of your answer. If you are asked to prove a result, please write a complete proof at the level of detail and rigor expected in prior CS Theory classes (i.e. 103). When writing proofs, please strive for clarity and brevity (in that order). Cite any sources you reference. 1 (18 points) Carry Heaps In this problem, we will develop a data structure, which we call a “Carry Heap”, H that stores a set S of at most n elements that have integer key values and supports two operations: • H.FindMin: return the element in S of minimum key and • H.Insert(x, k): insert x into H with key k. H is implemented as follows. H contains an array A of length 1 + log n. For each index i, A[i] is either NIL or is a rooted tree on 2i nodes. Assume that A is augmented such that it can access, for any nonNIL A[i], the next non-NIL entry of A after A[i] in constant time 1 . The elements of S are stored in the nodes of the trees stored in A. Every tree T stored in A is min-heap ordered, i.e. for every node x of T, key(x) ≥ key(parent(x)). To insert an element x with key k into H, we create a new singleton carry heap Hx as follows. To create Hx, we will create an all-NIL array Ax in constant time, and then set Ax[0] to be a tree with a single node x with key k. Then, we call a subroutine, meld(H, Hx) called on two carry heaps. The meld operation merges two arbitrary H and H0 and stores the answer into H. It works as follows. Let carry be a variable initially set to NIL, and let A and A0 be the arrays of H and H0 , respectively. Starting with i = 0, while i ≤ log n, consider the variables carry, A[i], and A0 [i]. • If at least two of the three variables are non-NIL, i.e. at least two are trees of size 2i , call these two T, T 0 and call the remaining one Q (which may be a tree of size 2i or NIL). Then, set A[i] = Q. If key(T.root) key(T 0 .root) merge T and T 0 into a new tree T + with root T.root by adding an edge from T.root and T 0 .root. Otherwise, mer