HW#1 --- last modified February 10 2019 22:34:37.

Solution set.

Due date: Feb 13

Files to be submitted:
  Hw1.zip

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.

1. Suppose we have a sample space of `n` coin tosses. Give a construction of a set of `n+1` events in this sample space which are `n`-wise independent. Prove your construction works.
2. A injection `f:[n] -> [m]` (here [n] is the set `{1, 2,..., n}`) where `n <= m`, is a function such that if `x ne y` then `f(x) ne f(y)`. Let `F_{n,m}` be the space of all such functions. Give pseudo-code for a randomized algorithm which generates elements of `F_{n,m}` uniformly at random. So for example, the random permutation algorithms from class do this for the case `n=m`, I want you to figure out a way to do it for all `n <= m`. Estimate the number of bits of randomness used by your algorithm and the run time of your algorithm in terms of `n` and `m`.
3. Consider the Hiring Problem from class. Candidate `i` had a `\r\a\n\k(i)` which was a number from `1` to `n`. Each candidate had a distinct rank. Rather than using a rank suppose the candidates had a fitness number `\f\i\t(i)` saying how good the candidate was. Suppose each candidate has a distinct fitness number between `1` and `n`, but that we only hire a candidate if they are 2 times better than the current best candidate. Calculate how this would effect the analysis of the expected number of candidates we hire.

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