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