Homework Assignment #2 Solution

Question 1. (10 marks)




In this question, you must use the insertion and deletion algorithms as described in the \Balanced Search Trees: AVL trees" handout posted on the course web site.




Insert into an initially empty AVL tree each of the following keys, in the order in which they appear in the sequence: 0, 25, 19, 5, -2, 28, 13, -5, 2, 6, 14, 7.




Show the resulting AVL tree T . (Only the nal tree should be shown; any intermediate trees shown will be disregarded, and not given partial credit.)




From AVL tree T , delete 2, and show the resulting tree.




In the two trees you must show the key and balance factor of each node.




Question 2. (20 marks)




In the following, B1 and B2 are two binary search trees such that every key in B1 is smaller than every key in B2.




Describe an algorithm that, given pointers b1 and b2 to the roots of B1 and B2, merges B1 and B2 into a single binary search tree T . Your algorithm should satisfy the following two properties:




Its worst{case running time is O(minfh1; h2g), where h1 and h2 are the heights of B1 and B2.



The height of the merged tree T is at most maxfh1; h2g + 1.



Note that the heights h1 and h2 are not given to the algorithm (in other words, the algorithm does not \know" the heights of B1 and B2). Note also that B1, B2 and T are not required to be balanced.




Describe your algorithm, and justify its correctness and worst-case running time, in clear and concise English.




Note: Partial credit may be given for an algorithm that runs in O(maxfh1; h2g) time.




Question 3. (24 marks)




The task in this question is to compute the medians of all pre xes of an array. As input we are given the array A[1 : : n] of arbitrary integers. Using a heap data structure, design an algorithm that outputs another array M[1 : : n], so that M[i] is equal to the median of the numbers in the subarray A[1 : : i]. Recall that when i is odd, the median of A[1 : : i] is the element of rank (i + 1)=2 in the subarray, and when i is even, the median is the average of the elements with ranks i=2 and i=2 + 1. Your algorithm should run in worst-case time O(n log n).




a. (20 marks) Describe your algorithm in clear and concise English, and also provide the corresponding pseudocode. Argue that your algorithm is correct.




b. (4 marks) Justify why your algorithm runs in time O(n log n).



[The questions below will not be corrected/graded. They are given here as interesting problems that use material that you learned in class.]




Question 4. (0 marks) This question is about the cost of successively inserting k elements into a binomial heap of size n.




Prove that a binomial heap with n elements has exactly n (n) edges, where (n) is the number of 1's in the binary representation of n.



Consider the worst-case total cost of successively inserting k new elements into a binomial heap H



of size jHj = n. In this question, we measure the worst-case cost of inserting a new element into H as the maximum number of pairwise comparisons between the keys of the binomial heap that is required to do this insertion. It is clear that for k = 1 (i.e., inserting one element) the worst-case cost is O(log n). Show that when k log n, the average cost of an insertion, i.e., the worst-case total cost of the k successive insertions divided by k, is bounded above by constant.




Hint: Note that the cost of each one of the k consecutive insertions varies | some can be expensive, other are cheaper. Relate the cost of each insertion, i.e., the number of key comparisons that it requires, with the number of extra edges that it forms in H. Then use part (a).

































































































































3