[SOLVED] algorithm CSC263H1, Fall 2019 Problem Set 2

CSC263H1, Fall 2019 Problem Set 2
General instructions
CSC263H1: Problem Set 2
Due Tuesday September 24 before 10pm
Please read the following instructions carefully before starting the problem set. They contain important information about general problem set expectations, problem set submission instructions, and reminders of course policies.
Your problem sets are graded on both correctness and clarity of communication. Solutions that are technically correct but poorly written will not receive full marks. Please read over your solutions carefully before submitting them.
Each problem set may be completed in groups of up to three. If you are working in a group for this problem set, please consult the articles on collaboration and plagiarism on posted on quercus.
Solutions must be typeset electronically, and submitted as a PDF with the correct filename. Hand- written submissions will receive a grade of ZERO.
The required filename for this problem set is problem set2.pdf.
Problem sets must be submitted online through CrowdMark. If you havent used CrowdMark before, give yourself plenty of time to figure it out, and ask for help if you need it! If you are working with a partner, you must form a group on CrowdMark, and make one submission per group. I didnt know how to use CrowdMark is not a valid excuse for submitting late work.
Your submitted file(s) should not be larger than 9MB. You might exceed this limit if you use a word processor like Microsoft Word to create a PDF; if it does, you should look into PDF compression tools to make your PDF smaller, although please make sure that your PDF is still legible before submitting!
Submissions must be made before the due date on CrowdMark.
The work you submit must be that of your group; you may not use or copy from the work of other
groups, or external sources like websites or textbooks.
Additional instructions
Lorem ipsum.
Page 1/3

CSC263H1, Fall 2019 Problem Set 2
1. [10 marks] Heaps. 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 1. You can use operations from the textbook 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).
Page 2/3

CSC263H1, Fall 2019 Problem Set 2
2. [20 marks] Expected cost. Consider a min-priority queue Q implemented using a binary min-heap. Let k N be a given natural number. Suppose that Q contains n = 2k 1 elements (or nodes), with indices 1 . . . n. Let aj be the value stored in the element with index 2j1.
Let x Z be a given integer. Let m be a random variable corresponding to the number of swaps performed by Q.insert(x).
Letpbeagivenrealnumber,0