1a. Algorithm: a. Find median. b. rotate to the root c. call on subtrees Want to prove: P(n): When done, the resulting tree has depth at most log n. We will prove this by strong induction on the number of elements (n) in the BST. Basis: n=1 or n=2. The trees have depth 0 and 1, respectively. This is log n in each case. Induction Hypothesis: Assume for all k such that k < n, P(n) holds. Induction Step: We now have to prove P(n). Applying the algorithm, we get two subtrees S1 and S2 each with at most n/2 elements. By the IH, the algorithm balances out both S1 and S2 each with depth at most log(n/2). Hence, the new tree we have will have depth at most log(n/2) + 1 when we add the median at the root, and log(n/2) + 1 = log n. 1b. Let n be number of nodes in given tree and T(n) the worst-case running time of this algorithm. The algorithm splits the tree into two subtrees of equal size and make recursive call. Thus the recurrence relation for T(n) is given by T(n) = 2T(n/2) + f(n), where f(n) is the worst-case running time of steps (i) + (ii). Step (i) can be done by traversing the tree, which takes O(n) time. Step (ii) also takes O(n) time because rotation is a constant time operation and it is done no more than n (= # of nodes) times. So f(n) = cn for some constant c. Using the Master Theorem (case 2 with a=b=2), we have T(n) = O(n log n). For the lower bound, we exhibit for infinitely many n a tree of n nodes on which the algorithm makes Omega(n log n) rotations. Such a tree is given by a single path of n nodes in which each node besides the root is a right child of its parent. * \ * \ * \ * \ * \ * \ * Call this tree t(n). It takes n/2 rotations to bring the median to the root, after which we are left with the tree * / \ * * \ \ * * \ \ * * Note that the two subtrees of the root are t(n/2), and we apply the algorithm recursively on these subtrees. So we can argue inductively that the number of rotations R(n) is >= n/2 log n: R(n) = n/2 + 2R(n/2) >= n/2 + 2(n/4)log(n/2) induction hypothesis = n/2(1 + log(n/2)) = n/2 log n. 2. Solution A. Inserting the k-th B0 takes time proportional to the index of the first unoccupied cell in the array. By analogy with binary addition, this is equal to the position of the first 0 in the binary representation of k, which is also equal to the number of bits that are flipped when adding 1 to k in binary. k binary rep. of k position of least significant 0 - ---------------- ------------------------------- 0 ...00000 1 1 ...00001 2 2 ...00010 1 3 ...00011 3 4 ...00100 1 5 ...00101 2 6 ...00110 1 7 ...00111 4 8 ...01000 1 ... Note that the lowest order bit is flipped every time, the next bit is flipped every 2nd time, the next every 4th time, etc. Thus a bound on the total number of flips is n + n/2 + n/4 + n/8 + ... = 2n. Thus the total time for inserting n B0 trees is O(n). Solution B. The time to insert a single B0 can be counted as (i) constant time for each link, plus (ii) constant time for storing the resulting tree in the array. Let us count the time taken under (i) and (ii) separately. For (ii), the n trees require O(1) time for each tree, or O(n) in all. For (i), the total time is O(number of links in all). But there can be at most n links in all, because for each link, there is one fewer parentless tree. Thus the total time is O(n) + O(n) = O(n). 3. Maintain two Fibonacci heaps, using two identical sets of nodes (one set for each heap). One is an original heap and the other one is a modified version where the heap-order is reversed, i.e. the maximum value among all vertices of any subtree is found at the root of that subtree. This modified heap also has a pointer max to the tree whose root has the maximum value. For both heaps, each node will have a pointer to its twin. Makeheap, insert, meld and delete: we have to do the operation on both heaps, so the time is doubled. Findmin: called on the original heap. O(1) Findmax: similar to findmin, and is called on the modified heap. O(1) Deletemin: we also have to delete the twin node on the modified heap. O(logn) Deletemax: similar to deletemin. It is called on the modified heap. We also have to delete the twin node on the original heap. O(logn) 4. Solution A. For this solution, we assume constant-time Boolean operations and shifts on bit strings of arbitrary length. For each node in the tree, we will compute three binary integers pos(n), depth(n), mask(n). The first represents the node's position in the tree, the other two represent its depth in the tree. These are defined recursively: pos(root) = 0 depth(root) = 1 mask(root) = 0 and for any node n, pos(leftchild(n)) = pos(n) pos(rightchild(n)) = pos(n) + depth(n) depth(leftchild(n)) = depth(rightchild(n)) = leftshift(depth(n)) mask(leftchild(n)) = mask(rightchild(n)) = leftshift(mask(n)) + 1 Example: for a node n at depth 3 from the root obtained by following the path left-right-right down from the root, the binary representations of pos(n) and depth(n) would be pos(n) = ...000110 depth(n) = ...001000 mask(n) = ...000111 These bit strings can be computed in O(n) time by doing a preorder tree walk. Now a is an ancestor of d if pos(d) & mask(a) = pos(a). That is, the path from the root to a, represented by the bits in pos(a) corresponding to the nonzero bits of mask(a), are the same as the corresponding bits of pos(d). For example, say pos(a) = ...00000000110 mask(a) = ...00000000111 pos(d) = ...00001010110 mask(d) = ...00001111111 Then d is a descendant of a, since the bits 110 representing the path down to a is a suffix of the bits 1010110 representing the path from the root down to d. Thus pos(d) & mask(a) = ...00001010110 & ...00000000111 = ...00000000110 = pos(a). Solution B. This solution involves integers instead of bit strings and assumes constant-time arithmetic on integers of arbitrary size. However, if you look at the binary representation of the integers, you will see that it is essentially the same as Solution A. For each node n in the tree, we will compute a positive integer pos(n) that uniquely describes the position of n in the tree and a number depth(n) that is the length of the path from the root down to n in the tree. Define pos(root) = 1 depth(root) = 0 pos(leftchild(n)) = 2*pos(n) pos(rightchild(n)) = 2*pos(n)+1 depth(leftchild(n)) = depth(rightchild(n)) = 1+depth(n). Note that for any node n, pos(parent(n)) = pos(n)/2 (integer division, discarding fractional remainder). The numbers pos(n) and depth(n) can be calculated by a preorder traversal of the tree in O(n) time. It can be shown by induction that the number pos(n) identifies the position of n in the tree uniquely, and that d is a descendant of a if and only if depth(d) >= depth(a) and (*) pos(d)/2^(depth(d)-depth(a)) = pos(a) (integer division, discarding fractional remainder). Surely depth(d) >= depth(a) is a necessary condition for d to be a descendant of a, so assume that depth(d) >= depth(a). We want to show that under this assumption, d is a descendant of a if and only if (*) holds. Basis: if depth(d)=depth(a), then (*) says pos(d)=pos(a), therefore d=a. Induction step: if depth(d) > depth(a), then depth(parent(d)) >= depth(a) and d is a descendant of a <=> parent(d) is a descendant of a <=> pos(parent(d))/2^(depth(parent(d))-depth(a)) = pos(a) induction hypothesis <=> (pos(d)/2)/2^(depth(d)-1-depth(a)) = pos(a) <=> pos(d)/(2*2^(depth(d)-1-depth(a))) = pos(a) <=> pos(d)/2^(depth(d)-depth(a)) = pos(a).