Question 3: This is a long question. Don't be intimidated! As always, for each part in this question, you must justify your answer. Professor Justin Bieber needs a data structure that maintains a collection A,B,C, of sets under the following operations: 1. Maximum(X) : return the largest element in the set X. 2. InSERT(X,y) : add the number y to the set X. 3. ExtractMax (X) : delete and return the largest element in the set X. 4. Combine (X,Y) : take the union XY of the sets X and Y, and call the resulting set X. Professor Bieber knows how to support the first three operations: Store each set X in a max-heap. The fourth operation seems to be more problematic, because we have to take two max-heaps and combine them into one max-heap. To support all four operations, Professor Bieber has invented the following sequence B0,B1,B2, of trees, which are now universally known as Bieber trees: 1. B0 is a tree with one node. Question 3.1: Let i0. How many nodes does the tree Bi have? Question 3.2: Let i0. What is the height of the tree Bi ? Question 3.3: Let i1. Prove that the subtrees of the root of Bi are the Bieber trees B0,B1,,Bi1. Let X be a set of n numbers, assume that n1, and let n=(bm,bm1,,b1,b0) be the binary representation of n. Note that bm=1 and n=i=0mbi2i. The Bieber max-heap for the set X is obtained as follows: 1. Partition the set X, arbitrarily, into subsets such that for each i for which bi=1, there is exactly one subset of size 2i. For example, if n=11=23+21+20, the set X is partitioned into three subsets: one of size 23, one of size 21, and one of size 20. 2. Each subset of size 2i is stored in a Bieber tree Bi. Each node in Bi stores one element of the subset. Each node in Bi has pointers to its parent and all its children. There is a pointer to the root of Bi. 3. Each Bieber tree has the property that the value stored at a node is larger than the values stored at any of its children. 4. The roots of all these Bieber trees are connected using a doubly-linked list. The figure below gives an example when n=11. Question 3.4: Let X be a non-empty set of numbers, and assume that this set is stored in a Bieber max-heap. Describe an algorithm that implements the operation MaximUM (X) in O(logX) time. Question 3.5: Let X and Y be two sets of numbers, and assume that both sets have the same size 2i. A Bieber max-heap for X consists of one single Bieber tree Bi. Similarly, a Bieber max-heap for Y consists of one single Bieber tree Bi. Describe an algorithm that implements the operation Combine(X,Y) in O(1) time. Question 3.6: Let X and Y be two non-empty sets of numbers, and assume that X is stored in a Bieber max-heap and Y is stored in a Bieber max-heap. Describe an algorithm that implements the operation Combine(X,Y) in O(logX+logY) time. Hint: This operation computes one Bieber max-heap storing the union XY. If you take the sum of two integers, both given in binary, then you go through the bits from right to left and keep track of a carry bit. Question 3.7: Let X be a non-empty set of numbers, and assume that this set is stored in a Bieber max-heap. Describe an algorithm that implements the operation INSERT(X,y) in O(logX) time. Note that this operation computes a Bieber max-heap for the set X{y}. Question 3.8: Let X be a non-empty set of numbers, and assume that this set is stored in a Bieber max-heap. Describe an algorithm that implements the operation ExtraCTMAx (X) in O(logX) time. Note that this operation computes a Bieber max-heap for the set X\{y}, where y is the largest number in X. Question 3.9: Let X be a non-empty set of numbers, and assume that this set is stored in a Bieber max-heap. How would you extend this data structure such that the operation Maximum (X) only takes O(1) time, whereas the running times for the other operations
