Generating Random Permutations

Suppose you need to generate a random permuation of the first N integers. For exampe, {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 generarates integers between i and j with equl 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 wehn 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 algorthm. [login to view URL] the array such that a[i] = i +1. Then for(i = 1; i<n; i++) swapReferences(a[i], a[ randInt (0,i) ] ); a) Prove that all three algorithms generate only legal permutations and that all permuatations are equally likely. b) Give ass accurate (big -Oh) an analysis as you can of the expected running time of each algorithm. c) Write seperate programs to execute each algorithm 10 times, to get a good average. Run Program(1) for N=250,500,1000,2000; program(2) for N = 2500, 5000, 10000, 20000, 40000, 80000; and program (3) N = 10000, 20000, 40000, 80000, 160000, 320000, 640000. d) Compare your analysis with the actual running times. e) What is the worst-case running time of each algorithm? ## Deliverables 1) Complete and fully-functional working program(s) in executable form as well as complete source code of all work done. 2) Deliverables must be in ready-to-run condition, as follows (depending on the nature of the deliverables): a) For web sites or other server-side deliverables intended to only ever exist in one place in the Buyer's environment--Deliverables must be installed by the Seller in ready-to-run condition in the Buyer's environment. b) For all others including desktop software or software the buyer intends to distribute: A software installation package that will install the software in ready-to-run condition on the platform(s) specified in this bid request. 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 Use Java, should run on Textpad and Windows.