Homework Assignment #2 Solution

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. Speci cally, 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 gure 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


30




30


10

45

10

45

10

45
7
15
33
50
7
15
33
50
7
15
33
50


20
47

20

47


20
47


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 elds: 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 speci ed in that subquestion (where h is the height of the BST rooted at root).

    a. Give an e  cient 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, de ne 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 e cient 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 e  cient 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 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).

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 di er by at most 1, i.e., if jHeight(lchild(v)) Height(rchild(v))j 1 (where the height of an empty subtree is de ned 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 elds: 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(minfh1; h2g), where h1 and h2 are the heights of B1 and B2.

    2. 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.

Hint: First derive an algorithm that runs in O(maxfh1; h2g) time, and then optimize it.



4