Homework 2

1. 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?

2. 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.