C++ Program from Weiss Book

**Due Date: Sept 25 Assignment:** The problem is to generate a random permutation of the first N integers. So, if N=4 one possible answer is: {3,1,2,4} The following is not a correct answer because 3 is repeated and it doesn't include 1: {3,3,2,4} The assignment is to first implement 3 separate solutions to this problem using the following 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]. So, to fill a[0] there is nothing to check. Whatever random number you generate can be put in a[0]. To fill a[1] you need to generate a random number and then check that it isn't the same as the one in a[0]. This goes on until a[N-1] is filled. a[N-1] may take several tries to fill. The chance of generating a random number that hasn't already been assigned at a[N-1] is 1 out of N. #2. Same as #1 but keep an extra array called the usedarray. When a random number, r, is first put in the array a, set used[r] = 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 ) ] ); randInt( x, y) will return a random integer between i and j inclusive. Without implementing these algorithms it's possible to estimate their asymptotic complexity. The runtime of algorithm #1 is O(N2 log N), the runtime of #2 is O(N log N), and the runtime of #3 is O(N). The second part of the assignment is to empirically verify these estimates. You can do this by running the algorithms for increasing values of N and comparing the ratio of observed runtimes with predicted runtime. The easiest way to do this is with a table of values that looks something like: Alg1 N = 250, 500, 1,000, 2,000 Alg2 N = 2,500, 5,000, 10,000, 20,000, 40,000, 80,000 Alg3 N = 10,000, 20,000, 40,000, 80,000, 160,000, 320,000, 640,000 ## Deliverables The three main deliverables are: (1) your source code, (2) the table of values that show results converging to a constant, and (3) a write-up of your analysis of the results. In your analysis be sure to include for each implementation brief comments to help us understand your solution. 3) All deliverables will be considered "work made for hire" under U.S. Copyright law. Buyer will receive exclusive and complete copyrights to all work purchased. (No GPL, GNU, 3rd party components, etc. unless all copyright ramifications are explained AND AGREED TO by the buyer on the site per the coder's Seller Legal Agreement). ## Platform Windows