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

## Introduction

See the general rules about assignments in this course.

DUE: 2018-02-07, 09:15 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. 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.