Week 8: Thursday (Saturday)
---------------------------

Q1. (40)

In a group of n people, the probability that at least two people will have their
birth day (not date of birth) on the same day and the same month is given by
    1 - (365/365) * (364/365) * ... * ((365-n+1)/365) 
ignoring leap years, i.e., assuming that there are only 365 days in a year.

Write a function that returns the minimum n for which this probability is at
least 0.5. Print this number.

Write another function that generates a set of n random birth days. Assume n to
be the constant found by the previous function. Check whether any two birthdays
in the set is the same. This function should return the answer.

In the main() function, generate 100 such random datasets. Count the number of
datasets for which there exists at least two birthdays that are common. Print
this number.

Use the function rand() that returns a random integer. You can use this
function to generate a random integer within a particular range. For example,
to generate a random integer between 1 and 10, you need to use (1 + rand() %
10).

Q2. (60)

Here is a description of an algorithm called the bubble sort that, given an
array of n numbers, sorts them in ascending order.
	1. Starting at the first position, traverse through all the elemnts of the
	   array.
		- If the element at the current position is greater than the element at
		  the immediate next position, then swap these two elements.
	2. Do this for all positions up to n-1.
	3. If there was at least one swap in the previous iteration, then go back
	   to the first step. Otherwise, the array is sorted.

For example, suppose n = 5 and the input array is: 4 8 2 5 1

First iteration:

    4 8 2 5 1
    (Current position is 1; 4 is not greater than 8; do nothing.)
    (Current position is 2; 8 is greater than 2; swap 8 and 2.) 
    4 2 8 5 1
    (Current position is 3; 8 is greater than 5; swap 8 and 5.)
    4 2 5 8 1
    (Current position is 4; 8 is greater than 1; swap 8 and 1.)
    4 2 5 1 8

Second iteration:

    4 2 5 1 8
    (Current position is 1; 4 is greater than 2; swap 4 and 2.)
    2 4 5 1 8
    (Current position is 2; 4 is not greater than 5; do nothing.)
    (Current position is 3; 5 is greater than 1; swap 5 and 1.)
    2 4 1 5 8
    (Current position is 4; 5 is not greater than 8; do nothing.)

Third iteration:

    2 4 1 5 8
    (Current position is 1; 2 is not greater than 4; do nothing.)
    2 4 1 5 8
    (Current position is 2; 4 is greater than 1; swap 4 and 1.)
    2 1 4 5 8
	... no more swaps ...

Fourth iteration:

    2 1 4 5 8
    (Current position is 2; 2 is greater than 1; swap 2 and 1.)
    1 2 4 5 8
	... no more swaps ...

Fifth iteration:

	... no swaps ...

Stop.

Write a program that implements bubble sort. The function should print the
array contents before each iteration.

In the main function, declare an array of size 8; ask the user to enter 8
integers into the array. Apply the sort function on this array.