To hand in on paper in class:
Rosen, Section 6.1, pp. 398-49: Exercises 10, 28, and 36
Section 6.2, p. 415, Exercises 8, 12, and 16
To hand in electronically (by 11:30 on the 11th):
The "coupon collector problem" (see Exercise 29 on p. 445) is an important model of sampling from an unkown domain. Suppose there are n different coupons that can be collected. Each time you make a purchase you get a random coupon, which may or may not be identical to one you already have. You'd like to estimate how many different coupons you're likely to have after getting a total of t coupons by writing a Perl program to simulate this process.
The program should ask the user to enter n (the number of different coupons), the total number of random coupons generated in a simulation, and the number of simulations to run. Each simulation should repeat the following t times:
For example, if the random values generated in a run are 4, 1, 4, 5, 1, 2 the hash would contain {1, 2, 4, 5} and the list would be (1, 2, 4, 6) indicating that new coupons were seen at steps 1, 2, 4, and 6.
The whole process should be repeated the number of times specified by the user, and the average values in the lists printed out. For example, if the second simulation generated the random values 1, 3, 4, 3, 1, 4 giving the list (1, 2, 3), the averages 1, 2, 3.5, and 6 would be printed.
Submit your well-documented program online using the command
provide comp14 hw8 progname.pl
The assignment is worth 100 points, 60 for the first part and 40 for the program.