Computer Science CSC263H

September 11, 2024

Homework Assignment #2

Due: September 25, 2024, by 11:00 am

Question 1. (20 marks)   Let H be a binomial heap that intially contains n keys (i.e.,  |H| = n).  In this question, you will determine the “amortized” (i.e., average) cost of successively inserting k keys into H.

a. Recall that α(n) is the number of 1’s in the binary representation of n.  Prove that binomial heap H has exactly n - α(n) edges.

Hint:  See Appendix B.5 about trees in our CLRS textbook.

b. We define the worst-case cost of inserting a new key into H to be the maximum  number  of pairwise comparisons  between keys that is required to do this insertion.

Consider the worst-case total cost of successively inserting k keys into H.  It is clear that for k = 1 (i.e., in-serting only one key) the worst-case cost is O(log2 n).  Show that when k > log2 n, the average cost of an in-sertion,i.e., the worst-case total cost of the k successive insertions divided by k, is bounded above by constant.

Hint:  Relate the cost of an insertion with the number of edges that it creates and use Part a.

Question 2. (20 marks) Part I.

In the following, 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.

Part II.

Your task here is to design a data structure called  Ultra-Heap that supports the following operations:

• Insert(k): inserts the key k into the Ultra-Heap,

• ExtractMax(): removes a max key from the Ultra-Heap,

• ExtractMin(): removes a min key from the Ultra-Heap,

• Merge(D ,D′ ): merges Ultra-Heaps D and D′ into one Ultra-Heap.

The worst-case running-time of each operation must be O(log n) where n is the total number of items.

c. Describe your Ultra-Heap data structure in clear English.  Your description should include any new information that you add to existing data structures that you use.

d. Explain how you implement each operation of Ultra-Heap in clear English. Hint: Use binomial heaps and your solution to Part I.

Question 3. (20 marks)   Give a linear-time algorithm that determines if a Binary Search Tree (BST) is an AVL tree (i.e., whether it satisfies the balance property of 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. Explain why its worst-case running time is Θ(n). Your algorithm will be graded by its correctness, running time,  simplicity, and clarity.

[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)

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.

Question 5. (0 marks)

A path between two nodes u,v in a Binary Search Tree (BST), is a sequence of distinct edges connecting a sequence of adjacent nodes in this 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.

In this question, you must derive an algorithm that, given any two keys in a BST, computes the lenght of the path between these two keys in the tree. To do so, 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.

For each of the following subquestions, first describe your algorithm in clear and concise English, and then give the pseudocode.  Then 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.

PathLength(root,k, m):     Given the root  of a BST, and two distinct keys k and m, return the length of the path between node(k) and node(m). Assume that the keys k and m are present in the BST.

For example, if root is the root of the BST in Figure 1, then PathLength(root, 15, 45) should return 3, and PathLength(root, 50, 47) should return 1.

The worst-case time complexity of your algorithm should be O(h). Hint: Use the procedures from Parts a and b.