2. (a) [Algorithm 1]
Each time this algorithm generates a new random number, it checks the
number against every number already in the array A. The new number is
added only if it is not a duplicate. In this way we are guaranteed that
there will be no duplicates in A. Assuming RandInt(i,j) is correct, only
legal values (in the range [1,N]) will be generated. Finally, since the
array has N slots, every number from 1 to N must be represented. Thus
only legal permutations are generated.
[Algorithm 2]
This algorithm differs from the previous one only in how it checks for
duplicates. Each time it generates a new random number, it looks it up
in the Used array to check if it is already in A. If so, it discards the
number and tries again. If not, it sets the Used value to 1 and adds the
number to A. In this way we are guaranteed that there will be no
duplicates. Thus only legal permutations are generated.
[Algorithm 3]
On the first pass this algorithm will fill A with the numbers 1 to N in
order. The second pass just swaps array elements without actually
changing which values are in A. Thus, A will contain exactly the numbers
1 to N with no duplicates, and this is a legal permutation.
(b) For this part (and part (e) as well) we shall assume that the random
number generator is truly random and that it runs in constant time.
[Algorithm 1]
It will take O(1) time to fill A[0] because it is impossible to generate a
duplicate at that stage. For each successive k, the probability of NOT
generating a duplicate is (N-k)/N. Thus, the expected number of trials
required to fill A[k] is N/(N-k). To find a duplicate in the array (if a
duplicate exists), we must look through half the array, on average, but
for the purposes of asymptotic analysis we may treat this as O(k).
Therefore, the expected time to fill A[k] is O(k*N / (N-k)) = O(N *
(k/(N-k)) ). Hence, the total expected time, T1, for the algorithm is on
the order of N * ( 1/N + 1/(N-1) + 2/(N-2) + ... + (N-2)/2 + (N-1)/1 ).
We can derive a lower bound for this by considering just the second half
of the series and rounding all the numerators down to (N/2): T1 >= N * (
(N/2)/1 + (N/2)/2 + (N/2)/3 + ... + (N/2)/(N/2) ) = N*(N/2) * ( 1/1 + 1/2
+ 1/3 + ... + 1/(N/2) ) = c*N*(N/2)*log(N/2). Thus, T1 is Omega(N^2 log
N). Similarly, we can derive an upper bound by considering the whole
series and rounding all the numerators up to N: T1 <= N * ( N/1 + N/2 +
N/3 + ... + N/N ) = N*N * (1/1 + 1/2 + 1/3 + ... + 1/N) = c*N*N*log(N).
So T1 is also O(N^2 log N), and now we can conclude that the expected
running time of this algorithm is Theta(N^2 log N).
[Algorithm 2]
The analysis of this algorithm is exactly the same as above, except that
it takes only constant time to determine if a duplicate exists. Hence,
the expected time required to fill A[k] is O(N/(N-k)). Therefore, the
total expected time, T2, is N * ( 1/N + 1/(N-1) + ... + 1/3 + 1/2 + 1/1 )
= c*N*log(N). Thus, the expected running time of this algorithm is
Theta(N log N).
[Algorithm 3]
This algorithm makes two passes through the array. The first pass
requires constant time at each element because it just assigns a numerical
value to that array element. The second pass performs one call to Swap
and one call to RandInt at each element. If we assume that Swap takes
only constant time, then this pass also requires only constant time at
each element. Thus, the total expected running time of this algorithm is
Theta(N) + Theta(N) = Theta(N).
(e) [Algorithm 1]
The worst case running time of this algorithm is infinite. The reason
for
this is because RandInt may consistently fail to generate the number 1,
and then we will never be able to fill our array. Of course, the
probability of this occurring is 0, but it is still possible and thus it
is our worst case.
[Algorithm 2]
The worst case running time of this algorithm is also O(infinity) for the
same reasons as for Algorithm 1.
[Algorithm 3]
The worst case for this algorithm is the same as the expected case,
because the algorithm will always perform the same steps independent of
any randomness.