Homework 2

Due Wednesday, January 22 at 5:00 PM. Please refer to the homework policy here.

  1. Use the recursion tree method to solve the following recurrence.

  2. Given an array of integers length , and some integer , design and analyze an algorithm that finds the smallest elements in time.

  3. Recall from class the randomized algorithm quick-sort, which sorts a list of numbers in expected time. In this problem, we design a similar problem for selecting the median, or more generally, the rank element (i.e., the th smallest element), from an array of numbers.

    We take as input an array of integers . Given an index between 1 and , the goal is to find the th largest number in . Note that is not sorted. One simple time algorithm is to sort , and return the th number in the sorted list. Our goal is to do better.

    The high level algorithm is similar to quick-sort. Each iteration we pick a random number in the array as a pivot, and divide the array into the set of numbers smaller than the pivot, and the set of numbers larger than the pivot. Then we will know the rank of the pivot in the array, and be able to deduce if the number we are looking for is either smaller than the pivot, equal to the pivot, or to the right of the pivot. Then we can recurse appropriately.

    1. Give a pseudocode implementation of the randomized selection algorithm described above.
    2. Show that this randomized selection algorithm takes time in expectation.