Homework 1

  1. Given n distinct numbers a1, a2, ..., an. 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:
      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?

Otfried Cheong