Suppose you need to generate a random permutation of the ?rst N integers. For example, {4, 3, 1, 5, 2} and {3, 1, 4, 2, 5} are legal permutations, but {5, 4, 1, 2, 1} is not, because one number (1) is duplicated and another (3) is missing. This routine is often used in simulation of algorithms. We assume the existence of a random number generator, r, with method randInt(i,j), that generates integers between i and j with equal probability. Here are three algorithms:

1. Fill the array a from a[0] to a[N-1] as follows: To ?ll a[i], generate random numbers until you get one that is not already in a[0], a[1], ..., a[i-1].

2. Same as algorithm (1), but keep an extra array called the used array. When a random number, ran, is ?rst put in the array a, set used[ran] = true. This means that when ?lling a[i] with a random number, you can test in one step to see whether the random number has been used, instead of the (possibly) i steps in the ?rst algorithm.

3. Fill the array such that a[i] = i+1. Then for( i = 1;i n; ++i )swap( a[ i ], a[ randInt( 0,i)] );

a. Prove that all three algorithms generate only legal permutations and that all permutations are equally likely.

b. Give as accurate (Big-Oh) an analysis as you can of the expected running time of each algorithm.

c. Write (separate) programs to execute each algorithm 10 times, to get a good average. Run program (1) for N = 250, 500, 1,000, 2,000; program (2) for N = 25,000,  50,000,  100,000,  200,000,  400,000,  800,000;  and  program (3) for N = 100,000, 200,000, 400,000, 800,000, 1,600,000, 3,200,000, 6,400,000.

d. Compare your analysis with the actual running times.

e. What is the worst-case running time of each algorithm?