Homework 1

1. Given n distinct numbers a₁, a₂, ..., a_n. How many permutations are there where the ith element is larger than the previous i - 1 elements? Give an exact bound as a function of n and i.
2. In the class we gave the following algorithm:

     RandomPermutation(A)
     Input: An array A[1..n]
     Output: The same array is permuted randomly
     for k = n downto 2
         i = random number between 1 and k
         exchange A[k] and A[i]
   

   Show that this algorithm is no longer correct if we replace "random number between 1 and k" by "random number between 1 and n".
3. The algorithm RandomPermutation in the previous problem computes a random permutation of n elements in linear time. This algorithm needs a random number generator that can produce a random integer between 1 and n in constant time. Now assume we have a restricted random number generator available that can only generate one random bit (0 or 1) in constant time. How can we compute a random permutation with this generator? How much time does this take? Is this optimal?