Random Permutations 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 using the given program permutations.cpp as a template. Your implementation of each algorithm should be limited to modification of functions algorithm1, algorithm2, and algorithm3 that appear as the last functions in permutations.cpp. You may also write any supporting function you need; if you do, place them directly above algorithm1. Make no modifications to lines 1 through 126 of the given source file with the exception of adding your name to the first line comment. 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. For part c, implement the three algorithms in functions algorithm1, algorithm2, and algorithm3; do not write separate programs for each. When you turn in your assignment, turn in your modified permutations.cpp source file and a document (PDF or Word format) showing your responses to the various parts of the exercise.

Answer only part C in c++ using the teachers program below #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 algorithm1(vector& v); void algorithm2(vector& v); void algorithm3(vector& v); bool verify_values(const vector& v); int main(int argc, char* argv[]) { // Set precision for timer output. cout  1) algo = atoi(argv[1]); else { cout > algo; } // Get size of vector from command line if provided, else prompt for it size_t size = 0; if (argc > 2) size = size_t(atoi(argv[2])); if (!size) { cout > size; } // Create vector of the given size vector v(size); // Fill vector with a random permutation of values from 1 through size Timer t; switch (algo) { case 1: algorithm1(v); break; case 2: algorithm2(v); break; case 3: algorithm3(v); break; default: cout   2.8 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 <>