- Given n distinct numbers a
_{1}, a_{2}, ..., 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. - 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". - 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