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 analyze the running time of the overall algorithm in terms of n and k.
(a) First sort the numbers using a comparison-based sorting algorithm, and thenreturn the k smallest numbers.
(b) 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 algorithm for integers, to sort strings? Please explain the modifications.
(b) Illustrate how your algorithm sorts the following list of strings[“BATURAY”, “GORKEM”, “GIRAY”, “TAHIR”, “BARIS”].
Please show every step of your algorithm.
(c) Analyze the running time of the modified algorithm.
1
