Description
Question 1 (Heap). Illustrate all intermediate steps (as a sequence of binary trees) for the
operation Insert(A, 20) applied to the max heap A = [18, 13, 9, 5, 12, 8, 7, 4, 0, 6]. [10 points]
Question 2 (Heap). The function Increase key(A, i, k) has the following pseudocode.
function Increase key(A, i, k)
Require: A[1..n] is a max heap.
Require: 1 ≤ i ≤ A.heap size is an index of A.
Require: k ≥ A[i] is a real number.
1: A[i] ← k
2: while i > 1 and A[parent(i)] < A[i]:
3: swap A[i] and A[parent(i)]
4: i ← parent(i)
Note that each swap operation on line 3 typically requires three assignments.
temp ← A[i]
A[i] ← A[parent(i)]
A[parent(i)] ← temp
Show how the idea of the inner loop of Insertion Sort can be used to reduce these three
assignments down to just one assignment, for this function Increase key(A, i, k). [10 points]
Question 3 (Binary trees). The binary-search-tree property and the min-heap property are
two properties that can describe binary trees.
(i) Can a binary tree with at least 3 nodes with distinct key values satisfy both properties?
Justify your answer. [2 points]
(ii) Let A be a min heap with n elements. Is it possible to print out the keys of all n elements
of A in sorted order in O(n) time? If this is possible, please show how. If this is not
possible, explain why not. [4 points]
(iii) Explain in detail why if a node in a binary search tree has two childern, then its successor
has no left child and its predecessor has no right child. [4 points]
Question 4 (Binary search tree). (i) We can sort a given set of n numbers by first building
a binary search tree containing these numbers (using tree-insert repeatedly to insert the
numbers one by one) and then printing the numbers by an inorder tree walk. What are
the worst-case and best-case running times for this sorting algorithm? [5 points]
1
(ii) Describe a binary search tree with n nodes, such that the average depth of a node in the
tree is Θ(log n) but the height of the tree is Ω(log n). Given an asymptotic upper bound
on the height of a binary search tree with n nodes, in which the average depth of a node
is Θ(log n). [5 points]
Question 5 (AVL Tree). Suppose that a, b, c, d, e, f, g, h are eight elements with the key values
38, 22, 33, 25, 47, 30, 28, 31 respectively. Starting with an empty AVL tree (i.e. with no nodes),
insert the elements a, b, c, d, e, f, g, h in this given order (where a is the first element to be
inserted) into the AVL tree, and let T be the final AVL tree obtained after the insertion of all
eight elements. Assume that for every insertion, the AVL tree remains as an AVL tree.
(i) Please draw T, and please also draw all seven intermediate AVL trees obtained in this
sequence of insertions. [4 points]
(ii) Let T1 be the AVL tree obtained by deleting element g (which has key value 28) from T.
Please draw T1, and please show all intermediate steps by drawing. [3 points]
(iii) Let T2 be the AVL tree obtained by deleting element e (which has key value 47) from T.
(Note that T still has element f.) Please draw T2, and please show all intermediate steps
by drawing. [3 points]
Question 6 (BSTs and AVL trees). (i) The binary tree shown in Fig. 1 is a BST, but not
an AVL tree. Explain why this BST is not an AVL tree, and perform the necessary
rotations, so that it becomes an AVL tree. Please indicate clearly all rotation steps,
including the node used for each rotation step. Please also draw all intermediate trees
obtained in your sequence of rotations, as well as the final AVL tree. (Note that a rotation
step is either Left Rotate(node) or Right Rotate(node). For simplicity, assume that
the elements of this BST are labeled by their key values, e.g. node 22 has key 22, node
49 has key 49, etc.) [10 points]
Figure 1: AVL Tree for Question 6(i)
(ii) Design an algorithm Tree Merge(T, T0
), where the two inputs T, T0 are binary search
trees, and where the output is a “merged” binary search tree consisting of all elements in T
and T
0
, possibly with repeated key values. You may write your algorithm in pseudocode.
Explain in as much detail as possible why the binary-search-tree property is still maintained after running your algorithm. What is the complexity of your algorithm? Justify
your answer. [15 points]
2
Question 7 (Analysis of d-ary heaps). As mentioned in Lecture L0301 Slide 23, we define a
d-ary heap (for d ≥ 2) analogously like a binary heap, but instead, in the d-ary tree visualization
of a d-ary heap, we allow every node to have at most d children. In this question, you will extend
several binary heap operations to the case of d-ary heaps. When asked to design an algorithm,
you may write your algorithm in pseudocode.
(i) For a d-ary heap A, given to us in its array representation, describe and explain how its
d-ary tree visualization can be obtained. Please give an example involving a 3-ary heap
with 15 elements. [5 points]
(ii) What is the height of a d-ary heap with n elements? Find an exact expression for this
height in terms of n and d, and justify your answer with details. [5 points]
In Week 3, we introduced several heap operations, including Extract Max(A), Insert(A, x),
and Increase Key(A, i, k), where A was assumed to be a binary max heap.
(i) Design an efficient algorithm that extends Extract Max(A) to d-ary max heaps A[1..n].
Your algorithm should return an element with the largest key and remove it from the input
array A. (If there are multiple elements with the same largest key value, then returning
any of these elements would be okay.) Analyze the running time of your algorithm in
terms of d and n. [5 points]
(ii) Design an efficient algorithm that extends Insert(A, x) to d-ary max heaps A[1..n], where
x is an element to be inserted into A while still maintaining the d-ary max heap data
structure. (Assume that x has a valid numerical key value x.key.) Analyze the running
time of your algorithm in terms of d and n. [5 points]
(iii) Design an efficient algorithm that extends Increase Key(A, i, k) to d-ary max heaps
A[1..n]. Here, A is assumed to be a d-ary max heap, i is an index of A, and k is a value.
Your algorithm should flag an error if k < A[i], but would otherwise set A[i] = k and
then update the d-ary max heap data structure appropriately. Analyze the running time
of your algorithm in terms of d and n. [5 points]
3
