468 words - 2 pages

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

Need help finding an example assignment?