- The following randomized algorithm selects the rth smallest
element in the interval A[i..j] of an unsorted array
A[1..n]. For example, to find the smallest element in the entire
array, you would call
*RandomSelect(A, 1, n, 1)*, to find the median element, you would call*RandomSelect(A, 1, n, n/2)*:RandomSelect(A, i, j, r) p = random(i, j) // random integer with i <= p <= j k = Partition(A, i, j, p) // partition array s = k - i + 1 // position of pivot in interval if r < s return RandomSelect(A, i, k-1, r) else if r > s return RandomSelect(A, k+1, j, r - s) else return A[k]

The subroutine*Partition(A, i, j, p)*compares A[p] with each element in A[i..j], and rearranges the elements into three parts. It returns the*new*index of the pivot element A[p].What is the

*exact*probability that*RandomSelect*compares the ith smallest and jth smallest element in the input array? (The correct answer is a simple function of i, j, and r.)What is the expected running time of

*RandomSelect*, as a function of n and r? Can you give the exact number of comparisons?What is the expected number of times that

*RandomSelect*calls itself recursively? - Implement the insert, delete, find, merge, and split methods for randomized treaps in a programming language of your choice. Perform tests and comment how well the data structure performs. Count the number of comparisons, estimate the expected number and the standard deviation.

Otfried Cheong