HW#1 --- last modified February 06 2019 04:20:16..Due date: Feb 11
Files to be submitted: Purpose: To gain experience with probabilistic analysis and our first randomized algorithms. Related Course Outcomes: The main course outcomes covered by this assignment are: LO1 -- Analyze or code a randomized algorithm Specification: This homework will consist of two parts, a written part and a coding part. Both parts will be submitted in the Hw1.zip file. The written part should be in a file Hw1.pdf. It should be typeset in a reasonable manner using a tool like LaTeX. For this part of the homework you should write solutions for the following questions. In what you turn in, first copy and paste the question, then write your solution to it beneath it.
For the coding portion of this assignment, I want you to write a program GenerateAllPermutations.java. I, as the grader, will compile your submission from the command line using: javac GenerateAllPermutations.java I have Java 7 installed on my laptop (no fancy Java 8 please). I will then run your program with various lines like: java GenerateAllPermutations n mode Here `n` is some positive integer and mode is either quiet or verbose. In verbose mode, your program should output a sorted list of all the permutations on the numbers 1 to n followed by the number of times a static method randomPermutation(n) was called during execution. For example, java GenerateAllPermutations 3 verbose 123 132 213 231 312 321 9 If the mode is quiet then it just outputs the number of times randomPermutation(n) was called. To implement GenerateAllPermutations, I want you to implement int[] randomPermutation(n) using one of the algorithms from class for computing a random permutation. Then in a loop call this function and see if the returned permutation is one you have already found or not. If not, store it. Once `n!` distinct permutations have been found your program sorts these and outputs as described. Using your program, I would like you to conduct some experiments, write them up, and include these in Hw1.pdf as well as your answers to the written problem. For the first experiment, plot a graph of the number of calls to randomPermutation(n) as a function of `n`. For each value of `n` you plot do at least 10 trials and compute a standard deviation. I would also like you to plot standard deviations as a function of `n`. What can you conclude from these graphs? Do your results agree with what you'd expect from the coupon collection results from class? Point Breakdown
|