Description

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 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 largest numbers.
(b) First use an order-statistics algorithm to find the k’th largest number, then partition 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 algorithm for integers, to sort strings? Please explain the modifications. (b) Illustrate how your algorithm sorts the following list of strings
.
Please show every step of your algorithm.
(c) Analyze the running time of the modified algorithm
1