CSCI 103 Fall 2017 Introduction to Programming

CSCI 103 Fall 2017: Introduction to Programming

Zombie-pocalypse

In this assignment you will use a computer program to help investigate the pressing question: How long might I survive once the zombie-pocalypse starts?  This program will require you to utilize the following knowledge and skills:

The Problem:

In a population of N people of which k are initially zombies, how many nights are required before the entire population (all N people) become zombies if the following conditions hold:

Setting up the Solution

While we can attempt to solve this problem analytically, let us instead use the computer to "simulate" the problem to find the answer.  Suppose we have an array, pop, of length N that stores bool's representing the population, where the i-th entry represents person i from the population. pop[i] will equal true if that person IS a zombie and false, otherwise. The first k entries in the array will be zombies while the remaining N-k will be human. For each zombie we can randomly choose someone to bite (who may or may not already be a zombie), changing them to a zombie if they were human. This would represent one night. We could repeat this process on a second night, third night, fourth night, and so on, counting the number of nights it takes until the entire population is a zombie.

By using the computers random number generator we can simulate zombie bites and count how many nights it takes until the population is all zombies.  However, the answer we obtain would be largely influenced by the random number generation, since the numbers we generate will determine if a zombie bites a human or another zombie (and thus another human is safe).  We can easily see that if the zombies get "lucky" (from the zombie's perspective), it may take a small number of nights to bite all remaining humans while an "unlucky" sequence of random values may mean a large number of nights before the population is all zombies, since they end up biting each other more often.  To account for this issue, we will use the law of large numbers to perform not just 1 simulation of the zombi-pocalypse, but MANY (say, M).   We can then use the average  number of nights taken for each of the M simulations of the zombie-pocalypse to arrive at our answer.  In addition, it may be interesting to find the range of answers over the M simulations, meaning what was the smallest (minimum) number of nights any zombie-pocalypse simulation required and what was the largest (maximum) number of nights any zombie-pocalypse simulation required. You should track these values as you perform the simulations and output them with the average.

To control the repeatability of our random simulations we will allow a seed value to be provided by the user.  This seed value will be supplied to the random number generator so that execution of the program multiple times using the same seed will result in the same sequence of random numbers (and thus same answer).

Input / Output

Based on the description above your program should take in the following input values (in the order shown) from the user.  The inputs may be typed on one line and separated by whitespace.

Your output should be the average, maximum and minimum number of nights until the entire population is a zombie. It should be formatted as:

Average Nights: avg-nights
Max Nights: max-nights
Min Nights: min-nights

Here are three sample runs of the program: the emphasized text is the part that the user typed in and the $ is the command-line prompt.

$ ./zombies
Enter the following: N k M seed
20 2 10000 137957
Average Nights: 7.3054
Max Nights: 16
Min Nights: 4
$ ./zombies
Enter the following: N k M seed
100 5 10000 137957
Average Nights: 10.0351
Max Nights: 19
Min Nights: 7
$ ./zombies
Enter the following: N k M seed
100 10 10000 371
Average Nights: 8.9769
Max Nights: 18
Min Nights: 6

Skeleton

We have provided a skeleton (starter code), located at

http://bytes.usc.edu/files/cs103/zombies/zombies.cpp

Download this file to your computer, e.g.,
$ wget http://bytes.usc.edu/files/cs103/zombies/zombies.cpp
then edit it.

You'll notice we declare an array pop to represent the population. In a normal program, the size of this array would match the population size entered by the user. However, since statically declared arrays must be of a constant size (known at compile time), we allocate a LARGE array that will be big enough to handle the large population we will test your code with. In your program you should only use the first N locations in that array.

Readme

Answer the experimental questions that are listed in the readme file, located at

http://bytes.usc.edu/files/cs103/zombies/readme.txt

Download this file to your computer, e.g.,
$ wget http://bytes.usc.edu/files/cs103/zombies/readme.txt
then edit it (fill in your name and email address) and submit the edited version with your code.

Style

You must follow all of the code style guidelines posted here.

Submit

Use the link on the coursework page to submit your code and readme file. It will run some basic tests to check your formatting. To check it more exhaustively, it would be a good idea for you to try running it on additional test cases.

Q&A

Credit to David Kempe for posing a version of this problem. Assignment created by Mark Redekopp.