Lab 8  Comp 170-201 -- Dordal/Nabicht -- Wed, October 23, 2002
Final version due Fri Nov 1


In this lab you will analyze the "Birthday Problem": given a random
selection of N people, what is the probability that two will have the
same birthday? In this lab you will use arrays as a problem-solving
tool, and also use appropriate functions to simplify the problem.

(Before turning it in, be sure to note the two extra items at the end,
after the ======.)

To do this, we simulate the random sample of N people with an array of
length N, filled with random numbers from g.nextInt(365), for a 
Random g. The numbers will all be in the range 0-364. Let's call the 
array bdays[].

First, fill bdays[] with random "birthdates". This represents *one* 
sample of N people; either there will be duplicate birthdays or not.  
As discussed below, we'll have to run this over and over. If N=50 
and we run this 100 times and 37 times we get duplicate birthdays 
and 63 times we don't, then we'll say that, with a random sample 
of N=50 people, the probability that two people have the same birthday 
is about 37%. (Numerically this is way wrong, as will become clear 
when you look at your data.)

After filling the array with random birthdates, *sort* the array. 
You may use L&L's Sorts class, if you wish. That's probably easiest:
        Sorts.selectionSort(bdays)
The Sorts class is on my web page.
        
Now, do the analysis. Figure out whether two people had the same 
birthday or not. This is true if there are two consecutive values 
in "bdays" with the same value. (They will be consecutive because 
you've sorted the array.) Here's a sample loop:
	boolean doubleflag = false;
	for (i=0; i<bdays.lenght-1; i++) {
		if (bdays[i] == bdays[i+1]) doubleflag = true;
	}
(How can you quit this loop as soon as you find a double birthday?)

This is just a single sample. Put all this (filling the array, 
sorting it, and looking for double birthdays) into a function, 
that returns, say, a boolean: true if two people had the same birthday, 
false if not. (Another approach is to return the *number* of duplicate 
birthdates: 0 if there weren't any, 1 or more if there were.) 
Let's call this function
	boolean bdayrun(int N)
(It's a little more convenient to make N alone the parameter. 
It is a little more *efficient* to make the array bdays[] the parameter, 
because that way you keep using the same array over and over in 
consecutive runs of bdayrun(); you don't have to keep allocating 
memory. Bear in mind, though, that I'm not really grading you on 
efficiency.)

(Another even slicker way to do all this is to create a *class* Bdays.
The constructor would (a) create the array bdays[], as private data,
(b) fill it with random birthdates, and (c) sort it. A member function,
isdouble(), would return whether there was a double birthdate in that
particular run.)

All this, remember, is *one* sample of N. Next, inside of another 
function, that takes N as a parameter, you should run this function 
RUNCOUNT times, say for RUNCOUNT = 1000 (use RUNCOUNT = 100 until 
you get things working). Report what fraction of the runs showed 
two people with the same birthday. Call this fraction P(N),
the probability of a dual birthday among N people.
Remember that this is a double, and that if you just evaluate
	count/RUNCOUNT
you'll be doing integer division, and will get the value 0. You need to
"cast" the numerator to type double before dividing:	
	((double) count) / RUNCOUNT

This leaves the choice of N. Print a table of the values of P(N) for 
N from 1 (where it had better be zero!) to 50. Past 50, print the 
value of P(N) that you get for N=60, 70, 80, ..., 200.

===================

Now let's consider the following:
    * triple birthdays: three or more people with the same birthday
    * double-doubles: two different days with two or more birthdays
Add to your program to find the probability of one of these (your 
choice), and find an N for which that probability is reasonably 
likely (at least 50%, but less than 90%).

Exercise question: (answer this in writing either in a program comment 
or in a separate file, but you don't have to implement it in Java):
In order to find whether there was a double birthday, we sorted the 
array. Describe a method for finding whether there was a double 
birthday (that is, two different values i and j such that 
bday[i] == bday[j]) *without* sorting.