HOMEWORK 4

Background: Ch. 10.

Due October 1st:

• 4.1: Give an algorithm for computing the mode of an unsorted list of numbers. Algorithm should run in $O(n \log n)$.

• 4.2: Give an algorithm and tight worst-case running time bounds for efficiently computing the rank of GPA x both when (a) the list L of GPAs is sorted and (b) when it is not.

• 4.3: Prove that the expected running time of randomized SELECT is O(n). Use the good split vs. bad split proof like the quicksort one we did in class.

• 4.4: CLR Exercise 10.3-3 (pg. 192).

• 4.5: CLR Exercise 10.3-7 (pg. 192). By ``closest,'' they mean ``closest in value.'' [Extra credit! Hint: You may need to ``select'' more than once.]