UNB/ CS/ David Bremner/ teaching/ cs3383/ assignments/ CS3383 Assignment 4


See the general rules about assignments in this course.

DUE: 2018-02-07, 09:15 in the assignment box.


In this assignment you are asked to mimic the analysis of randomized quicksort we covered in class in order to partially analyze randomized selection.

Consider the following randomized Select Algorithm (from the slides)

RandSelect (A, p, q, i)
    if p = q then return A[p]
    r ← RandPartition (A, p, q)
    k ← r – p + 1
    if i = k then
        return A[r]
    if i < k then
        return RandSelect (A, p, r – 1, i )
        return RandSelect (A, r + 1, q, i – k )
  1. Give indicator random variables that describe the choice of r

  2. Let T(n) denote the (random) running time of this algorithm. Use your indicator variables to prove that

     E[T(n)] ≤ (1/n) ∑ {  E[max(T(j-1), T(n-j))] | 1 ≤ j ≤ n } + O(n)
  3. Under the assumption that i>j implies T(i) > T(j) show that

    E[T(n)] ≤ (2/n) ∑ {   E[T(j)]| ⌊n/2⌋ ≤ j ≤ n -1 }  + O(n)
  4. Why is assuming that the random variable T(n) is monotone increasing stronger than with a deterministic recurrence?

  5. By comparing Q3 with the quicksort recurrence from class, prove that the expected running time of selection is strictly faster than that of quicksort.