## Description

## 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 then

return 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

[“V EY SEL00

, “EGE00

, “SELIN00

, “Y ASIN00].

Please show every step of your algorithm.

(c) Analyze the running time of the modified algorithm

1