Project 1a: Birthday Paradox

You will write a simple program to verify the Birthday Paradox. The Birthday Paradox states that if you randomly select 23 people, the probability of two people having the same birthday is around 50%. If you randomly select 70 people, the probability is around 99%.

You will write a simple program to verify the birthday paradox. This program should be invoked as follows:

 shell% ./paradox -i inputfile -o outputfile 

The above line means the users typed in the name of the program ./paradox and gave it two inputs: an input file (-i) called inputfile and an output file (-o) to put the results into called outputfile.

  1
 10
 20
 30
 40
 50
 70
164
229

Your goal: to build a program called paradox that takes in one of these input files, and for each N in the input file, output the probability that at least two people out of N randomly selected people will share the same birthday. The output should be sent to the output file. For the same input file shown above, the output would look like this:

0.00
0.12
0.42
0.69
0.90
0.96
1.00
1.00
1.00

Some Details

In each trial, you should use rand() to generate N random numbers in the range of 1 to 365 (representing the days of the year). Make sure you seed the random number generator using srand so that the random numbers vary across different trials. If any two of the generated random numbers match, the trial is positive.

In paradox, you will calculate the probability using 1000 trials.

Hints

In your paradox program, you can use different methods to read and write to files. One way would be to use FILE pointers. A good tutorial on how to use those can be found here. You can also access files using system calls such as open(), read(), write(), and close().

You should accept two arguments for the program: an input file (-i) and an output file (-o). You should use something similar to getopt() to parse the arguments.

To exit, call exit() with a single argument. This argument to exit() is then available to the user to see if the program returned an error (i.e., return 1 by calling exit(1)) or exited cleanly (i.e., returned 0 by calling exit(0)).

If you don't know how to use these functions, use the man pages. For example, typing man rand at the command line will give you a lot of information on how to use the library random number generator. Of course, you can also use Google to find information about the function online.

Assumptions and Errors

File length: There will be less than 1000 numbers in the input file.

Invalid files: If the user specifies an input or output file that you cannot open (for whatever reason), the program should EXACTLY print: Error: Cannot open file foo, with no extra spaces (if the file was named foo ) and then exit.

Too few or many arguments passed to program: If the user runs paradox without any arguments, or in some other way passes incorrect flags and such to paradox, print Usage: paradox -i inputfile -o outputfile and exit.

Important: On any error code, you should print the error to the screen using fprintf(), and send the error message to stderr (standard error) and not stdout (standard output). This is accomplished in your C code as follows:

fprintf(stderr, “whatever the error message is\n”);

General Advice

Start small, and get things working incrementally. For example, first get a program that simply reads in the input file, one line at a time, and prints out what it reads in. Then, slowly add features and test them as you go.

Testing is critical. One great programmer I once knew said you have to write 5-10 lines of test code for every line of code you produce; testing your code to make sure it works is crucial. Write tests to see if your code handles all the cases you think it should. Be as comprehensive as you can be. Of course, when grading your projects, we will be. Thus, it is better if you find your bugs first, before we do.

Keep old versions around. Keep copies of older versions of your program around, as you may introduce bugs and not be able to easily undo them. A simple way to do this is to keep copies around, by explicitly making copies of the file at various points during development. For example, let's say you get a simple version of paradox.c working (say, that just reads in the file); type cp paradox.c paradox.v1.c to make a copy into the file paradox.v1.c . More sophisticated developers use version control systems like CVS (old days) or mercurial or github (modern times), but we'll not get into that here (though you can, and perhaps should!).

Keep your source code in a private directory. An easy way to do this is to log into your account and first change directories into private/ and then make a directory therein (say p1, by typing mkdir p1 after you've typed cd private/ to change into the private directory). However, you can always check who can read the contents of your AFS directory by using the fs command. For example, by typing in fs listacl . you will see who can access files in your current directory. If you see that system:anyuser can read (r) files, your directory contents are readable by anybody. To fix this, you would type fs setacl . system:anyuser “” in the directory you wish to make private. The dot “.” referred to in both of these examples is just shorthand for the current working directory.