CMPS 101: HW2, Winter 2018
• All assignments must be submitted through git. Please look at the Piazza
guide on submitting assignments.
• LATEX is preferred, but neatly handwritten and scanned solutions will also
be accepted. Please submit as PDF.
• Solutions to the problems should be clearly labeled with the problem num-
ber.
• Although no points are given for neatness, illegible and/or poorly orga-
nized solutions can be penalized at the graders option.
• Clearly acknowledge sources, and mention if you discussed the problems
with other students or groups. In all cases, the course policy on collab-
oration applies, and you should refrain from getting direct answers from
anybody or any source. If in doubt, please ask the instructors or TAs.
Q1 (2 points): Heaps naturally lead to a sorting algorithm, Heapsort. Start-
ing from array A, build it into a min-heap. Repeatly called Extract-Min
to get the elements of A in sorted order. Give pseudocode for Heapsort
and show that it is not stable.
Q2 (2 points): Given an input array A of length n and a positive integer
k > 0, design an algorithm that outputs the largest k elements in sorted
order. Provide pseudocode and give a time-complexity analysis. You will
get full credit if the time-complexity is O(n+k log k). (If you get anything
less efficient, you only get 1 point.)
Q3 (1 point): Prove that the number of keys stored in a 2-3 tree of height h
is Ω(2h) and O(3h).
Q4 (2 points): Suppose you are given two 2-3 trees T1, T2 and a value x such
that all keys in T1 are less than x, and all keys...
