CS2104: Introduction to Problem Solving
Homework Assignment 15

Due at 8:00AM on Wednesday, December 07
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:

This assignment builds on the simulation program that you wrote for Homework 12. The program can be written in any programming or scripting language, such as Fortran, C, C++, awk, Java, Perl, Python, Mathematica, Matlab, etc. Your program needs to be sufficently well commented, with good style such as meaningful variable names, indentation, etc., so that it is easy to read and understand.

In the original program from Homework 12, as you generated your random numbers, you counted the number of failures until you reached a success, and then incremented the appropriate entry in an array. You will modify your program so that it can output the following information. For every 10 successes (and thus, 10 updates to the data collection array), you will output one line that states the percentage of successes (up to that point) that occurred with only one try. You will do this 200 times (for each 10 successes up to 2000 total successes recorded in the array). So you should end up with 200 lines each containing a single value.

You will then take these 200 lines of data and create a graph from them. If you wrote your program in something like Matlab or Mathematica, then you should be able to use the native graphing facility for this. If not, then you can just cut and paste the 200 lines into some graphing program, and generate a graph from that.

The key issues for this program are (1) modifying your previous program; (2) using a graphing tool to analyze data generated by a program that you wrote; and (3) getting a feel for the convergence rate for the probability of success after a single trial.

Your homework submission will include the source code for the program (simply copy this into your homework submission document), along with the graph of 200 data points. You should include your observations on how quickly the data value seems to be converging, based on what you see in the graph.

As an example, imagine that a given series of random numbers used to generate the first 10 successes resulted in 3 of the 10 succeeding in one try. At this point, 30% of the trials succeeded in one try, so your initial data point for the graph is at 30%. Now, if the next set of 10 successes happened to have none that succeeded on the first try, then your second line of data will be 3/20 or 15%. If your third set of 10 successes had two that succeeded on the first try, then your third line of data would be 5/30 or 16.67%.

Here is an example of the kind of graph that you should turn in. Of course the data values in the example graph do not look like the values that you should actually get from your program.