1. The following paper does a variety of interesting probabilistic analyses: P. Flajolet et.al., Birthday paradox, coupon collectors, caching algorithms and self-organizing search, Discrete Applied

Mathematics 39 (1992), 207-229. ( http://algo.inria.fr/flajolet/Publications/FlGaTh92.pdf ) It includes the following formula, which provides the expected number of coupons needed under a general discrete

probability distribution P for m coupons: m1 m1q 1

() 1P (14b) where PJ= Pi 1

q=0 J=q J iJ

Form=3 and (p1,p2,p3) = (a,b,c),the paper simplifies(14b)to:

111111 11a1b1c +1ab+1bc +1ca.

Your task is write a C program to 1) evaluate (14b) for the special case that k of the probabilities are the value p and the

other m - k probabilities are the value q and 2) implement a simple random simulation of generating coupons for this

situation.

2. Submit your C code on Canvas before 3:45 p.m. on March 3. Be sure to include comments regarding how to compile and

execute your code.

Getting Started:

1. m will not exceed 50. m is atleast 2.

2. The input is very simple:

1. The first input line is m and k. k must be larger than 0 and smaller than m.

2. The second line will have the value of the probability p for each of the first k coupons. p must be larger than 0 and

   such that k p is smaller than1. Each of the other m -k coupons will have a probability of q=(1-kp)/(m-k)

3. The third input line will be the number of times to execute a random simulation.

4. The fourth input line is a seed for the random number generator (e.g. srandom()). (The only significance of the

   seed is in the reproducibility of the experiments.)

3. Your power set approach should use Q(m2) time instead of the Q(2m) time needed by the original version of expression (14b). Elementary combinatorics(https://en.wikipedia.org/wiki/Pascal%27s_triangle)will be useful. You should output how many times innermost loop(s) execute for the theoretical part. The time for computing binomial coefficients should not be included.