Assignment #2 H denotes a binomial max heap

• For any question, you may use data structures and algorithms previously described in class, or in
prerequisites of this course, without describing them. You may also use any result that we covered
in class, or is in the assigned sections of the official course textbook, by referring to it.
• Unless we explicitly state otherwise, you should justify your answers. Your paper will be marked
based on the correctness and completeness of your answers, and the clarity, precision, and conciseness of your presentation.
• Your a2.pdf submission should be no more than 4 pages long in a 10pt font.
1
Question 1. (1 marks)
In this question, H denotes a binomial max heap, n is the number of items in H, x is (a pointer to the
node of) an item inside H, and k is a number (key).
a. Describe a simple algorithm to increase the key of a given item x in a binomial max heap H to
become k. Your algorithm should not change anything if k ≤ x.key. The worst-case running-time of your
algorithm must be O(log n). Give a high-level description of your algorithm in clear English.
b. Using part (a), describe a simple algorithm to delete a given item x from a binomial max heap H.
The worst-case running-time of your algorithm must be O(log n). Give a high-level description of your
algorithm in clear English.
Question 2. (1 marks)
Design a data structure called SuperHeap that supports the following operations:
• Insert(k): inserts the key k into the SuperHeap,
• ExtractMax(): removes a max key from the SuperHeap,
• ExtractMin(): removes a min key from the SuperHeap,
• Merge(D,D0
): merges SuperHeaps D and D0
into one SuperHeap.
The worst-case running-time of each operation in your data structure must be O(log n) where n is the total
number of items. Your data structure must be based on a data structure that we discussed in this course.
1. Explain the main high-level idea of your solution in clear English.
As part of this explanation, (1) state what is the underlying data structure that you are using in
your solution, and (2) explain clearly all the information that you are adding to this underlying data
structure. Specifically, what additional information are you storing in each node?
2. Give a high-level description in clear English of how to implement each operation of the SuperHeap.
Hint: Use binomial heaps and your solution to Question 1.
Question 3. (1 marks)
Two nodes in a Binary Search Tree (BST) are said to be t−away, if the length of the path between the two
nodes is at most t. A path between two nodes u, v in a tree, is a sequence of edges connecting a sequence
of adjacent nodes in the tree, where the starting node in the sequence is u and the ending node is v; the
length of a path is the number of edges in that path. Two distinct nodes u, v are said to adjacent if either
u is the parent of v or v is the parent of u. For example, the figure below shows the path between 15 and
45 (length 3), the path between 7 and 20 (length 3), and the path between 47 and 50 (length 1) in a BST.
30
45
50
47
33
10
15
20
7
30
45
50
47
33
10
15
20
7
30
45
50
47
33
10
15
20
7
2
To derive an algorithm to check whether two nodes of a BST are t−away, solve the three subquestions
outlined below.
Henceforth assume that root is not nil and the BST rooted at root does not have duplicate keys. Morever,
each node u of the BST has the following fields: key(u), containing the key of the node, lchild(u) and
rchild(u), containing pointers to u’s left and right children respectively; note that node u does not have a
pointer to its parent. For a key k in the BST, let node(k) be the BST node with key k.
Give pseudocode and a concise and clear English description of your algorithm for each of the following
subquestions. Also give a brief explanation of why your algorithm achieves the worst-case time complexity
specified in that subquestion (where h is the height of the BST rooted at root).
a. Give an efficient algorithm for the following procedure.
PathLengthFromRoot(root, k): Given the root of a BST and a key k, return the length of the path
between root and node(k). Assume that the key k is in the BST.
For example, if root is the root of the BST in Figure 1, then PathLengthFromRoot(root, 15)
should return 2, and PathLengthFromRoot(root, 47) should return 3.
The worst-case time complexity of your algorithm should be O(h).
b. Given the root of a BST and two distinct keys k, m present in the BST, define the FCP of k and m
in the BST rooted at root, to be the root of the subtree that is furthest away from root which contains
both k and m. In other words, the FCP of k and m is a node parent such that: (a) the subtree rooted
at parent has both the keys k and m in it, and (b) the length of the path between root and parent is the
maximum among all such parents. Give an efficient algorithm for the following procedure.
FCP(root, k, m): Given the root of a BST and two distinct keys k and m, return the FCP of k and m
in the BST rooted at root. Assume that both k and m are present in the BST.
For example, if root is the root of the BST in Figure 1, then FCP(root, 15, 45) should return the
node with key 30, FCP(root, 7, 20) should return the node with key 10, and FCP(root, 50, 47)
should return the node with key 50.
The worst-case time complexity of your algorithm should be O(h).
c. Give an efficient algorithm for the following procedure.
IsTAway(root, k, m, t): Given the root of a BST, two distinct keys k and m, and a non-negative
integer t, return true if the length of the path between node(k) and node(m) is at most t, and false
otherwise. Assume that k and m are present in the BST.
For example, if root is the root of the BST in Figure 1, then IsTAway(root, 15, 45, 3) should return
true, and IsTAway(root, 7, 20, 2) should return false.
The worst-case time complexity of your algorithm should be O(h).
Hint: Use the procedures from Parts a and b.
3
[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).
Question 5. (0 marks)
A Binary Search Tree (BST) T is an AVL tree if, for every node v of T, the heights of the left and right
subtrees of v differ by at most 1, i.e., if |Height(lchild(v)) − Height(rchild(v))| ≤ 1 (where the height of
an empty subtree is defined to be −1).
Give a linear-time algorithm that determines if a Binary Search Tree (BST) is an AVL tree.
The algorithm’s input is a pointer u to the root of a BST T where each node v has the following fields: an
integer key, and pointers parent, lchild and rchild to the parent, the left and right children of v in T (any
unused pointer is set to Nil). The algorithm’s output should be True if T is an AVL tree, and False
otherwise.
The worst-case running time of your algorithm must be Θ(n) where n is the number of nodes in T.
Describe your algorithm by giving its pseudo-code.
Question 6. (0 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.
Hint: First derive an algorithm that runs in O(max{h1, h2}) time, and then optimize it.
4