Homework 5

Due: June 5, 2025
Points: 100

1. (50 points) Now enhance your tic-tac-toe game to determine when the game is over — that is, there is a winner (three in a row, column, or diagonal) or a tie (no winner and all 9 squares on the board are full). Your program should exit with a status code of 0. Print the results on the standard output and errors on the standard error:
   • If X wins, print “Game over! X won!\n”;
   • If O wins, print “Game over! O won!\n”; or
   • If X wins, print “Game over! It's a tie!\n”.

   Call your program tttd.c. You can find an executable for it in the directory /home/bishop/hw5.

2. (50 points) The birthday problem asks how many people must be in a room so that the probability of two of them having the same birthday is 0.5. This problem has you explore it by simulation. Basically, you will create a series of lists of random numbers of length n = 2, …, and look for duplicates. You will do this 5000 times for each length. For each length, count the number of lists with at least 1 duplicate number; then divide that number by 5000. That is the (simulated) probability that a list of n generated numbers has at least one duplicate. As the random numbers you generate are between 1 and 365 (each one corresponding to a day of the year), this simulates the birthday problem.

   Now, breathe deeply and calm down. We will do this in steps; you only have to turn the final program in to Canvas (not Gradescope).

   1. First, detecting duplicates. Write a function called hasduplicates(bday) that takes an array bday and returns 1 if it contains a duplicate element, and 0 if it does not. For example, if bday is

      int bday[] = { 1, 2, 3, 4, 5, 5, 2 };
      

      then hasduplicates(bday) returns 1 and if

      int bday[] = { 1, 2, 3, 4, 5, 6, 7 };
      

      then hasduplicates(bday) returns 0.

   2. Now, deal with one set of birthdays. Write a function called onetest(count) that generates a list of count random integers between 1 and 365 inclusive, and returns 1 if it contains a duplicate element, and 0 if it does not. Please use the function hasduplicates(bday) to test for duplicates.

   3. Now for the probability for count people. Write a function probab(count, num) that runs num tests of count people, and counts the number of tests with duplicates. It returns the fraction of the tests with duplicates; that is, the number of duplicates divided by num.

   4. Now for the demonstration. Start with 2 people, and begin adding people until the probability of that many people having two people with a birthday in common is over 0.5. (In other words, start with a list of 2 elements, and increase the number of elements in the list until the simulation shows a probability of 0.5 that a number in the list is duplicated.) Print each probability; your output should look like this:

      For  2 people, the probability of 2 birthdays in common is 0.001400
      For  3 people, the probability of 2 birthdays in common is 0.006600
      For  4 people, the probability of 2 birthdays in common is 0.015200
      For  5 people, the probability of 2 birthdays in common is 0.025400
      For  6 people, the probability of 2 birthdays in common is 0.041400
      For  7 people, the probability of 2 birthdays in common is 0.053000
      For  8 people, the probability of 2 birthdays in common is 0.082000
      For  9 people, the probability of 2 birthdays in common is 0.092200
      For 10 people, the probability of 2 birthdays in common is 0.121800
      

      Hint: Don’t be surprised if your probabilities are slightly different than the ones shown in the sample output. As randomness is involved, it is very unlikely your numbers will match the ones shown here.

   To turn in: Please call your program bday.c and submit it through Canvas (not Gradescope). A sample executable is available on the CSIF in the directory /home/bishop/hw5.

Matt Bishop Office: 2209 Watershed Sciences Phone: +1 (530) 752-8060 Email: mabishop@ucdavis.edu

ECS 36A, Programming and Problem Solving Version of May 26, 2025 at 8:56AM

You can also obtain a PDF version of this.