Every two years, many people around the country wait in long lines to vote due, in part, to inadequate provisioning of voting booths. In this assignment you will write a simulator to help election officials determine how many voting booths should be allocated to a precinct to avoid long lines. For example, we might want to determine the minimum number of voting booths we can have to ensure that with a 99% probability 95% of our voters wait no longer than 20 minutes.
In Part 1, you built a set of classes for use in your polling place simulator. In Part 2, you will put those pieces together. In more detail, we want to determine how many voting booths a precinct requires given some information about that precinct (number of voters, average voting time, target wait time, etc...). To do this we will run several simulations with different numbers of voting booths and find which simulations succeed at meeting the wait-time requirements and which do not. To do this you will need to build a function to simulate a single election day and another function that runs multiple election day trials.
from within your <Your CNETID>-cs121/hw4b directory. We will try grade hw4a as quickly as possible. Once you get your commented code back, you should fix any problems we identify in your code. (Please change files you copied to hw4b, not the ones in hw4a.) We will look at your revised code as part of the process of grading hw4b.svn copy hw4a/Voter.java . svn copy hw4a/VoterSample.java . svn copy hw4a/VotingBooths.java .
S&W (p. 581) describe a program that simulates a single server, say a toll booth, that serves a queue of clients, say cars, that arrive with a specified distribution and have a fixed service time. You need to simulate multiple servers (voting booths) and variable service times (voting times), but the structure of your simulation will be very similar. There are two main differences. First, instead of generating arrival times for the clients during the simulation and storing them on a queue, you will simply generate a VoterSample and pull voters out of the sample as needed. Second, you will use an instance of the VotingBooths class to keep track of the current state of the voting booths. Your simulation code will be responsible for having voters enter and exit booths as appropriate. Note that this step is where you will determine the time that voters enter the voting booths.
Test your code using a small number of voters and booths. The file tests/t3.txt describes an experiment on a small precinct.
My implementation is about 25 lines of code (not including comments, etc).
Your task is to implement the function runTrials in Simulate.java, which will run a number of election day trials (using your electionDay function) to evaluate whether a specified number of voting booths is sufficient for a given precinct (as specified by an Experiment). Each trial will yield a VoterSample in which the voters have been assigned departure times. From this VoterSample, you can determine the percentage of voters who waited no more than the target waiting time given in the experimental parameters. Your function should run at least the minimum number of trails specified by the experiment and no more than the specified maximum number of trials. Within that range, your function should only run as many trials as needed to determine whether the precinct meets its target. Your function should return the number of trials run.
How do you know how many trials to run? The simplest method would be to run a fixed number of trials. If a given precinct is highly unlikely to meet the specified criteria, this method will likely run many more simulations than necessary. After running at least the minimum number of trials, your implementation should avoid doing unnecessary work by stopping when the z-score of the target percentage is greater than 2.
Here's a set of formulas for computing the z-score:
where xi is the percentage of voters who waited no longer than the target waiting time for trial Ti and T is the number of trials run thus far. There are better methods for determining when to stop, such as the t-test, but this method works well enough for our purposes.
Note: you will need a data structure to hold the results of the trials as you compute them.
My implementation of runTrials, including auxiliary functions, is about 50 lines of code (not including comments, etc).
We recommend checking in your code early and often.