CS13002 PDS Lab, Spring 2003, Section 1/A, Supplementary Lab Test

CS13002 PDS Lab, Spring 2003, Section 1/A

Supplementary Lab Test

[The birthday paradox]

Generate a random sequence of birthdays and store the birthdays in an array. As soon as a match is found, report that. Also report how many birthdays were generated to get the match.

Note:

Encode a day in the year by an integer between 0 and 364, where 0 refers to January 1, 1 to January 2, ..., 364 to December 31.
Generate a random sequence of integers (between 0 and 364) one by one and store the integers in an array. Every time a new random day is generated, it is compared against the entries currently stored in the array. If a match is found, report and exit.
Print the birthdays in the standard format (MonthName Date). Don't bother about leap years, i.e., assume that every February has 28 days and every year 365 days. In case you are not sure about the numbers of days in the months, use the following array:
```
int nDays[12] = {31,28,31,30,31,30,31,31,30,31,30,31};
```
Use srand to get different outputs on different runs.
There is no need to use dynamic arrays. But if you do so, I won't mind.

Sample output

 1. March 12
 2. November 27
 3. May 27
 4. July 2
 5. April 18
 6. September 11
 7. February 13
 8. October 27
 9. September 15
10. January 11
11. October 29
12. December 23
13. January 5
14. February 1
15. June 13
16. December 28
17. November 12
18. October 15
19. July 4
20. January 21
21. February 24
22. July 29
23. January 17
24. April 6
25. March 26
26. November 1
27. January 5
Match found among 27 birthdays.
Birthdays no. 13 and 27 are the same...

Remark

It is surprising to see that you usually require a very small number of people (around 25) in order to have a match in their birthdays. However counter-intuitive it might sound, it is a mathematical truth, commonly known as the birthday paradox. In short it says that if you draw (with replacement) about sqrt(n) samples from a pool of n objects, there is about 50/50 chance that you get a repetition. If you draw 2sqrt(n) samples, you can be almost certain that there will be at least one repetition. In order to know more about the paradox and its mathematics, click here.

[Course home] [Home]