$30.00
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 worstcase running time (e.g., which sorting algorithm? which orderstatistics algorithm?), and analyze the running time of the overall algorithm in terms of n and k.

First sort the numbers using a comparisonbased sorting algorithm, and then return the k largest numbers.

First use an orderstatistics 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 comparisonbased sorting algorithm.
Which method would you use? Please explain why.
Problem 2 (Lineartime 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 [\V EY SEL^{00}; \EGE^{00}; \SELIN^{00}; \Y ASIN^{00}]:
Please show every step of your algorithm.
(c) Analyze the running time of the modified algorithm
1