[Algo] Exercise 9.2

Exercise 9.2-1
Show that in RANDOMIZED-SELECT, no recursive call is ever made to a 0-length array.
solution:
When a 0-length array is made by partition, k must be either 1 or n. Recursive call will not be  made to a 0-length array unless we want 0-order statistic or (n+1)th order statistic.


Exercise 9.2-2
Argue that the indicator random variable $X_k$ and the value $T(\max(k-1, n-k))$ are independent.
solution:
Trivial. Occurrence of $X_k$ makes the time it takes to do the recursive call neither more nor less.


Exercise 9.2-3
Write an iterative version of RANDOMIZED-SELECT.
solution:

ITERATIVE-RANDOMIZED-SELECT(A, p, r, i)

1  while true

2    q = RANDOMIZED-PARTITION(A, p, r)

3    k = q - p + 1

4    if i == k

5      then return A[q]

6    else if i < k

7      then r = q - 1

8    else

9      p = q + 1

10     i = i - k

Exercise 9.2-4
Suppose we use RANDOMIZED-SELECT to select the minimum element of the array $A = \langle 3, 2, 9, 0, 7, 5, 4, 8, 6, 1\rangle$. Describe a sequence of partitions that results in a worst-case performance of RANDOMIZED-SELECT.
solution:
[3, 2, 9, 0, 7, 5, 4, 8, 6, 1]  --> [3, 2, 0, 7, 5, 4, 8, 6, 1] + [9]
[3, 2, 0, 7, 5, 4, 8, 6, 1] --> [3, 2, 0, 7, 5, 4, 6, 1] + [8]
[3, 2, 0, 7, 5, 4, 6, 1] --> [3, 2, 0, 5, 4, 6, 1] + [7]
[3, 2, 0, 5, 4, 6, 1] --> [3, 2, 0, 5, 4, 1] + [6]
[3, 2, 0, 5, 4, 1] --> [3, 2, 0, 4, 1] + [5]
[3, 2, 0, 4, 1] --> [3, 2, 0, 1] + [4]
[3, 2, 0, 1] --> [2, 0, 1] + [3]
[2, 0, 1] --> [0, 1] + [2]
[0, 1] --> [0] + [1]
[0]