Description
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 final 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:
1. Its worst–case running time is O(min{h1, h2}), where h1 and h2 are the heights of B1 and B2.
2. The height of the merged tree T is at most max{h1, h2} + 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(max{h1, h2}) time.
Question 3. (24 marks)
The task in this question is to compute the medians of all prefixes 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).
2
[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.
a. 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.
b. Consider the worst-case total cost of successively inserting k new elements into a binomial heap H
of size |H| = 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