CS3383 Assignment 3

‎

Introduction

For general information about assignments in this course, see assignments

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

The following randomized select algorithm omits the while loop of the version we analysed in class.

You can download runnable Python code for this algorithm.

def select2(A, p, q, i):
    n = q - p + 1
    if n==1: return A[p]
    loc = randrange(p,q) # choose random integer in [p,q)
    r = partition(A,p,q,loc) # See quicksort slides
    k = r - p 
    if (k == i): return A[r]
    if (i < k):
        return select2(A,p,r-1,i)
    else:
        return select2(A,r+1,q,i-k-1)

Consider the following recurrence for the running time of select2. There exist constants $c, n_0>0$ such that $\forall n\geq n_0$:

\begin{equation} \label{orge5beae5} T(n) \leq \sum_{j=1}^{n-1} X_j \max(T(j-1), T(n-j)) + cn \end{equation}

where

\begin{equation} \label{org014566c} X_j = \begin{cases} 1 & \text{if $r=j+p-1$}\\ 0 & \text{otherwise} \end{cases} \end{equation}

1. Indicator variables

Prove the expected value $E[ X_j ] = 1/n$. What assumptions do you need to make?

2. Expectation

Prove that

\begin{equation} \label{org7b85815} E[T(n)] ≤ (1/n) \sum_{j=1}^n E[\max(T(j-1), T(n-j))] + O(n) \end{equation}

3. Eliminating max

Under the assumption that $T(n)$ is strictly monotone increasing, i.e. that $i>j$ implies $T(i) > T(j)$ show that \eqref{org7b85815} implies

\begin{equation} \label{org81c6cea} E[T(n)] ≤ (2/n) \sum_{j=\lfloor n/2 \rfloor}^{n-1} E[T(j)] + O(n) \end{equation}

4. Discuss Assumptions

Why is assuming that the random variable $T(n)$ is strictly monotone increasing stronger than with a deterministic recurrence?

5. Compare with quicksort

In the quicksort slides we developed the following bound for quicksort:

\begin{equation} \label{org688d74d} E[Q(n)] \leq \frac{2}{n}\sum_{i=1}^{n-1} E[Q(j)] + \Theta(n) \end{equation}

Prove that the bound \eqref{org81c6cea} is strictly stronger than the bound \eqref{org688d74d} . The hard part (omitted in this assignment) is to see that the overall bound drops from $O(n\log n)$ to $O(n)$.