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

Introduction

See the general rules about assignments in this course.

DUE: 2016-10-13, 16:30 in the assignment box.

Questions

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 )
    else
        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. Explain why the assumption of question 3 is stronger here than it usually is.

  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.