CS301 Homework 2


Category: You will Instantly receive a download link for .zip solution file upon Payment


5/5 - (2 votes)

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