Use the copy-and-paste method to give an average-case analysis for the permute function in permute.cpp.

Assume that the random number generator used in the algorithm produces truly random numbers, i.e, for any integer j in the range 0 .. RAND_MAX, any given call of rand() has a probability 1/RAND_MAX of returning j.

The rand() function runs in O(1) time (worst-case and average).

Show all work!

Remember that you are doing average case analysis.

PDRIVER.CPP

#include  #include  #include  #include  using namespace std; void permute (int[], int); int main(int argc, char** argv) { if (argc != 3) { cerr << "When you run this program, you must supply two parameters. " << "The first is the size of the array you want to permute. " << "The second is the number of trials you want to perform. " << " " << "For example, if you called this program pdriver, you " << "might invoke it as: " << " pdriver 100 10 " << "to generate 10 random permutations of 100 elements each." << endl; return 1; } int N; int trials; { istringstream arg1 (argv[1]); arg1 >> N; istringstream arg2 (argv[2]); arg2 >> trials; } int *array = new int[N]; srand(time(0)); for (int t = 0; t < trials; t++) { permute (array, N); // for (int i = 0; i < N; ++i) cout << array[i] << ' '; cout << endl; } return 0; } PERMUTE.CPP 

#include  #include  #include  using namespace std; unsigned rnd(unsigned limit) { return rand() % limit; } // Generate a random permutation of the integers from // 0 .. n-1, storing the results in array a. // void permute (int a[], int n) { for (int i = 0; i < n; i++) { // Guess at a value to put into a[i] int guess = rnd(n); while (find(a, a+i, guess) != a+i) { // If it's one that we've already used, guess again. guess = rnd(n); } a[i] = guess; } }