Description
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.
- (a) First sort the numbers using a comparison-based sorting algorithm, and then return 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 algo- rithm 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
