Textbook Question

Suppose you need to generate a random permutation of the first 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 fill 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 first put in the array a, set used[ran] = true. This means that when filling 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 first 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. Exercises 73

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?

Teacher assignment

Please see exercise 2.8 on page 72 of the textbook. The problem presents three different algorithms for populating an array of size N with a random permutation of the values from 1 through N. Implement each of these three algorithms, each in a separate program, that uses the given program permute0.cpp as a template. Your implementation of each algorithm should be limited to modification of function generate_permutations that appears as the last function in permute0.cpp. You may also write any supporting function you need; if you do, place them directly above generate_permutations. The given program includes code to time your functions, and will report the number of seconds of CPU time required to execute your function. Complete parts a through e in the exercise. For part a, a formal proof is not necessary, but a short convincing argument will be fine. When you turn in your assignment, submit three C++ programs (each based on permute0.cpp) and a document (PDF or Word format) showing your responses to the various parts of the exercise.

Permute0.cpp

// Name: YOUR NAME HERE // CISC 230, Homework Assignment 2 #include #include #include #include #include #include using namespace std; // Class for finding execution time. // Usage: // Timer t; // Create a Timer object // some_stuff(); // Your code // double elapsed_time = t.seconds(); // Get executation time class Timer { private: clock_t clock_start; public: Timer() { reset(); } void reset() { clock_start = clock(); } double seconds() { return (double(clock()) - double(clock_start)) / CLOCKS_PER_SEC; } }; unsigned int randInt(); unsigned int randInt(unsigned int max); unsigned int randInt(unsigned int min, unsigned int max); void generate_permutations(vector& v); bool verify_values(const vector& v); int main(int argc, char* argv[]) { // Set precision for timer output. cout << fixed << setprecision(5); // Get size of vector from command line if provided, else prompt for it size_t size = 0; if (argc > 1) size = size_t(atoi(argv[1])); if (!size) { cout << "Enter vector size: "; cin >> size; } // Create vector of the given size vector v(size); // Fill vector with a random permutation of values from 1 through size Timer t; generate_permutations(v); double exec_time = t.seconds(); // Verify that the vector, in fact, contains the desired values cout << "Values in the vector are " << (verify_values(v) ? "valid" : "NOT VALID") << ". "; if (v.size() <= 25) for (size_t i = 0; i < v.size(); i++) cout << (i ? " " : "") << v[i]; cout << endl; // Report the run time cout << "Run time: " << t.seconds() << " seconds "; #ifdef _MSC_VER // If Microsoft Visual C++ compiler version is defined system("pause"); #endif return 0; } // randInt - Generates a random integer, three versions: // - Random integer (with RNG initialization) // - Random integer from 1 through max inclusive // - Random integer from min through max inclusive unsigned int randInt() { static bool init = true; // Initialize RNG? if (init) { srand(unsigned(int(time(NULL)))); init = false; } #if RAND_MAX == 32767 return rand() * rand(); #else return rand(); #endif } unsigned int randInt(unsigned int max) { return randInt() % max + 1; } unsigned int randInt(unsigned int min, unsigned int max) { return min <= max ? randInt(max - min + 1) + min - 1 : randInt(max, min); } // verify_values - Verifies that the given vector contains the values 1 // through the size of the vector. bool verify_values(const vector& v) { vector used(v.size(), false); for (size_t i = 0; i < v.size(); i++) if (v[i] && v[i] <= v.size()) used[v[i] - 1] = true; for (size_t i = 0; i < v.size(); i++) if (!used[i]) return false; return true; } // *** IF YOU NEED ADDITIONAL FUNCTIONS, ADD THEM HERE *** // *** MODIFY THIS FUNCTION FOR THE ASSIGNMENT *** // generate_permutations - Fill the given vector with the values 1 through // the size of the vector, with values arranged in some random permutation. void generate_permutations(vector& v) { for (size_t i = 0; i < v.size(); i++) v[i] = i + 1; }

C++ Only!!!