CSC263H, Winter 2024
Assignment 2
Due February 05, 2024 10 p.m.
. You may work in groups of no more than two students (groups of two are recommended), and you should produce a single solution in a PDF file named a2.pdf, submitted to MarkUs. Submissions must be typed. Please refer to the course information sheet for the late submission policy.
. Important Note: You may use, without proof, the results that are mentioned during the lec- tures/tutorials or in the course material (including properties and standard operations of data struc- tured discussed in the lecture and tutorial). Please do not repeat algorithms or runtime analyses from class, handouts, or the textbook—just refer to known results as needed.
1. Suppose the keys 1, 2, 3, 4, 5 are inserted in random order into a BST where each order of insertion is equally likely to occur. What is the average height of the resultant tree? We are looking for an exact numeric answer. Show your work.
Hint: Let H(n) be the average height of a BST with keys from {1,..., n} inserted in uniformly random order. Try to find H(n) using H(n − 1) and/or H(n − 2) and/or ..., and/orH(1) for each value of n.
2. Consider a max-priority queue Q implemented using a binary max-heap. We would like to design an ExtractSecondLargest(Q) operation, which returns the second largest key in Q and deletes it from Q. The worst-case running time of this operation must be in O(log n). We assume that all keys in Q are distinct integers.
(a) Write the pseudo-code of your ExtractSecondLargest(Q) algorithm. Let Q be an array whose indices start from 0. You can use operations from the course notes and lectures as helpers without describing their details.
(b) Explain why your pseudo-code works correctly. In particular, explain why the element you extract is the second largest one, and why this operation maintains the heap property.
(c) Explain why the worst-case running time of your algorithm is in O(log n).
Practice Question
The following question has been provided only for extra practice. It will NOT be marked. Please do NOT submit your answer for this question.
. Consider a data structure called Priority Binary Search Tree (PBST), described as follows:
– Each node x in the PBST has two attributes: x.priority and x.key. Both attributes are unique, i.e., there are no duplicate priorities or duplicate keys in the tree.
– A PBST is a valid binary search tree sorted by x.key.
– The x.priority attribute satisfies the max-heap property, i.e., every non-leaf node’s priority is larger than its children’s priorities.
Note that a PBST is not necessarily a nearly-complete binary tree as is a binary heap. Given a set of n nodes with distinct priorities and keys. Prove that there is a unique PBST containing these nodes. Hint: Use induction!