Homework 2 Solution



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 be-low, 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.

  1. First sort the numbers using a comparison-based sorting algorithm, and then return the k largest numbers.

  1. First use an order-statistics algorithm to find the k’th largest number, then par-tition 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 algo-rithm for integers, to sort strings? Please explain the modifications.

  1. 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