Homework submission A pdf copy of your own solutions to Problems 1 and 2 should be submitted at SUCourse.
Grading Full credit will be given to correct solutions that are described clearly.
Problem 1 (Order statistics) Suppose that you are given a set of n numbers. The goal is to find the k largest numbers in this set, in sorted order. For each method be-low, identify relevant algorithms with the best asymptotic worst-case running time (e.g., which sorting algorithm? which order-statistics algorithm?), and analyze the running time of the overall algorithm in terms of n and k.
First sort the numbers using a comparison-based sorting algorithm, and then return the k largest numbers.
First use an order-statistics algorithm to find the k’th largest number, then par-tition around that number to get the k largest numbers, and then sort these k largest numbers using a comparison-based sorting algorithm.
Which method would you use? Please explain why.
Problem 2 (Linear-time sorting) (a) How can you modify the radix sort algo-rithm for integers, to sort strings? Please explain the modifications.
Illustrate how your algorithm sorts the following list of strings [\V EY SEL00; \EGE00; \SELIN00; \Y ASIN00]:
Please show every step of your algorithm.
(c) Analyze the running time of the modified algorithm
1
