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 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 thenreturn 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 algorithm for integers, to sort strings? Please explain the modifications.
- Illustrate how your algorithm sorts the following list of strings[“BATURAY”, “GORKEM”, “GIRAY”, “TAHIR”, “BARIS”].
Please show every step of your algorithm.
- Analyze the running time of the modified algorithm.
1
