CS2984: Introduction to Problem Solving
Homework Assignment 12

Due at 11:00pm on Tuesday, November 6
50 Points

See the General Guidelines for homework assignments.

This assignment may optionally be done with a partner. You are strongly advised to use a partner. If you do use a partner, then:

I have an MP3 player that contains 1000 songs. The songs are from a wide variety of musical genres and artists. I like to use the "random" play feature on my player to play songs at random. Given that there are 1000 songs, I would like to know the answer to this question: How many songs will I need to play, on average, before I have heard every song at least once?

Your assignment is to write a short program to simulate this problem and generate an answer to the question. The program can be written in any programming language, such as C, C++, Java, Perl, Python, Matlab, Mathematica, etc. Your program needs to be sufficently well commented, with good style such as good variable names, indentation, etc., so that it is easy to understand. Your homework submission will include the source code for the program (simply copy this into your homework submission document), along with the answer for the expected number of songs that need to be played on average. Please note that this is number is likely to vary considerably from trial to trial. So you will need to run many iterations of the simulation before you can get a reliable estimate. Explain how you determined how many iterations you need to get a good answer.