# 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:
```  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?

Otfried Cheong