Chris Pollett>
Old Classes>
CS255 |
HW#1 --- last modified February 10 2019 22:34:37.Due date: Feb 13 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. 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 part of your homework I want you to write a program to conduct experiments related to the coupon collector's problem. Namely, I want you to experiment to see if the number of coupons needed to be collected really goes as `b(ln b+O(1))` and to determine what the constant in the `O(1)` is. You should code your project in either Java or Python and name your program either Coupon.java or Coupon.py. In the case where you use Java, I will compile your program from the command line using the command: javac Coupon.java Your program will then be run from the command using a command like either: java Coupon some_positive_integer or python Coupon.py some_positive_integer Your program will then enter a while loop until it has generated all integers from 0 to some_positive_integer - 1. In each iteration of the loop it will randomly pick a number from 0 to some_positive_integer - 1 and print it out followed by a newline. Once it is done, it will print "All coupons collected in x iterations". Here `x` should be the numbeer of times through the loop Below is an example of what the output might look like: java Coupon 4 0 3 2 0 2 1 All coupons collected in 6 iterations. Include your code as part of the Hw1.zip file you submit. Then conduct 10 experiments at each positive integer between 1 and 1000 (you can do this programmatically if you want). Determine the average number of iterations for each integer and its standard deviation. Plot the integers and the number of trials with the standard deviations on a clearly labeled graph where you fit the curve to the data using `chi^2` minimization. How well does the curve fit? What it the empirically determined constant in the `O(1)`? Write up your experiments and put the graphs in your Hw1.pdf file that you include in the Hw1.zip file you submit. Point Breakdown
|