Computer Science CSC263H
September 11, 2024
Homework Assignment #2
Due: September 25, 2024, by 11:00 am
|
• You must submit your assignment through the Crowdmark system. You will receive by email an invitation through which you can submit your work. If you haven’t used Crowdmark before, give yourself plenty of time to figure it out!
• You must submit a separate PDF document with for each question of the assignment.
• To work with one or two partners, you and your partner(s) must form a group on Crowdmark (one submission only per group). We allow groups of up to three students. Submissions by groups of more than three students will not be graded.
• The PDF file that you submit for each question must be typeset (not handwritten) and clearly legible. To this end, we encourage you to learn and use the LATEX typesetting system, which is designed to produce high-quality documents that contain mathematical notation. You can use other typesetting systems if you prefer, but handwritten documents are not accepted.
• If this assignment is submitted by a group of two or three students, for each assignment question the PDF file that you submit should contain:
1. The name(s) of the student(s) who wrote the solution to this question, and
2. The name(s) of the student(s) who read this solution to verify its clarity and correctness.
• By virtue of submitting this assignment you (and your partners, if you have any) acknowledge that you are aware of the homework collaboration policy for this course, as stated here .
• 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 (in lectures or tutorials) by referring to it.
• Unless we explicitly state otherwise, you should justify your answers. Your paper will be marked based on the correctness and efficiency of your answers, and the clarity, precision, and conciseness of your presentation.
• The total length of your pdf submission should be no more than 3 pages long in a 11pt font.
|
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.