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 smallest numbers in this set, in sorted order. For each method below, identify relevant algorithms with the best asymptotic worst-case running time (e.g., which sorting algorithm? which order-statistics algorithm?), and ana-lyze 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 smallest numbers.
First use an order-statistics algorithm to find the k’th smallest number, then partition around that number to get the k smallest numbers, and then sort these k smallest 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.
(b) Illustrate how your algorithm sorts the following list of strings
[\V EY SEL00; \ALI00; \SELIN00; \Y ASIN00; \ZEY NEP00]:
Please show every step of your algorithm.
(c) Analyze the running time of the modified algorithm.
1
