On Tuesday, many people around the country waited in long lines to vote due, in part, to precincts with an insufficient number of voting machines. In this assignment, you will write a program to help election officials determine how many voting machines should be allocated to a precinct to avoid long lines.
Specifically, you will write a program to simulate a queuing model for waiting times under different scenarios. We will provide code for representing voters and sampling from the distributions. You will write classes to represent the queue of voters waiting to vote, to represent the state of the voting machines, and to simulate an instance of our model. You will also write some generic library code that you can use to build both your waiting queue and your voting machines.
We have seeded your gforge account with a directory named a6 that contains the following files: Voter.java, ObsManager.java, Util.java, Precinct.java, VoterPQ.java, and Simulate.java. The directory a6 also contains a subdirectory of test data for precincts and experiments.
We have provided a class, Voter, that represents voters and models the varying rates at which voters arrive at the polls and of how long voters take to complete ballots. We assume that voters arrive independently and the length of time they take to vote is independent of other voters.
The file Voter.java implements a representation for Voters that has public instance variables for the voter's arrival time, voting time (time to complete a ballot), departure time, and voter number. It provides a function mkVoterSample to generate a sample of N voters with specified arrival and voting time rates. It also implements the function toString, which allows you to use the standard printing functions (println, etc) to print a Voter, and the function printVoterSample, which prints a sample of voters. See the Voter API for details.
You should not make any assumptions about the voter number, except that it will be unique within a given voter sample. It is provided merely for debugging purposes. Also, you should not make any assumptions about the order that voters appear in the sample.
Note: Voter.java uses a function from stdlib.jar, so you will need to include it in your CLASSPATH.
ObsManager.java implements a very simple class for tracking observations of a random variable. See the ObsManager API for details.
Util.java contains utility code that is used to parse data files.
You will implement the code for the remaining classes.
In this step, you will implement a data structure called a priority queue (in VoterPQ.java). A minimum priority queue is a data structure that supports the following operations:
Priority queues are also used to order items by maximum priority rather than minimum priority. Generics and interfaces can be used to write a general priority queue where the type of the priorities, the desired ordering, and the type of the items are specified at the time the priority queue is created. However, you should implement priority queue where the keys are integers and the items are Voters.
Priority queues are usually implemented with a data structure called a heap. We will talk about heaps in class at some point, but for this assignment, you should implement your priority queue as a linked list sorted by increasing order of priority. Items with duplicate priorities should be sorted in the order that they are inserted, oldest first.
We have provided skeletons for the necessary functions in in VoterPQ.java.
Test your code before moving on to the next step. Put your test code in the main function of VoterPQ.java. Your test cases should cover an empty PQ, a PQ with one item, a PQ with many items, and duplicate keys. Make sure to intermix the insertion and removal of items from the queue and to insert items not in sorted order. You might want to write a function that prints the contents of a priority queue in order as a debugging aid.
In this step, you will implement a class for representing precincts using the skeletons provided in the file Precinct. We have provided code that constructs a precinct object from a file. The format of that file is:
A precinct is defined by the number of voters, the voting time rate, and the number of hours the polling place is open. For our purposes, Precincts need to support two operations. The first, getNumVoters simply returns the number of voters in the Precinct.
The second, electionDay, simulates election day for the precinct for a specified number of voting machines and returns an array of voter waiting times. Your first step is to generate the day's distribution of voters by calling Voter.mkVoterSample to obtain an array of Voters and then insert them into a priority queue ordered by arrival time. Your second step is to set up a priority queue for tracking the current state of voters at the voting machines. This second priority queue should be ordered by departure time. The third step is to simulate the flow of voters through the machines to generate the waiting times.
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 machines) and variable service times (voting times), but the structure of your simulation will be very similar. There are three main differences. First, instead of generating arrival times for the clients during the simulation, you will simply pull them off your voter priority queue as needed. Second, you will use the machine priority queue to determine when the next machine will be free. And third, you will need to limit the number of machines in use to be no more than the number of machines the precinct owns.
Test your code using a small number of voters and machines. The files tests/P7 and tests/P8 describe small precincts. The function Voter.printVoterSample, which prints out the voters in a sample, maybe useful for debugging purposes.
Simulate runs a collection of experiments to determine the number of machines a precinct would need to meet certain goals. The parameters for an experiment are specified in a file with the following format:
Your task is to implement the function evaluatePrecinct in Simulate.java, which will run a number of trials to evaluate whether the waiting time at a given precinct is below a target threshold for a target percentage of voters. For example, for a given precinct, can we say with confidence that 90% of the voters will wait in line for under 10 minutes?
Each trial should simulate one election day for the precinct and then determine the percentage of voters whose waiting times were under the target waiting time. We refer to this value as the trial's observation.
To be specific, evaluatePrecinct takes a Precinct and an Experiment runs an appropriate number of trials, and returns an obsManager containing the observations from the trials. Your function should only run as many trials as needed (within the specified range of trials) to determine whether the precinct meets its target.
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, then this method may run many more simulations than necessary. After running at least the minimum trials, your implementation should avoid doing unnecessary work by stopping when the mean of the observations is more than two times the standard error of the mean of the observations away from the target percentage of voters. There are better methods for determining when to stop, such as the t-test, but this method works well enough for our purposes.
As noted earlier, the obsManager class, lets you record observations and then compute simple statistics on them, including mean and standard error of the mean.
We have supplied the main function for the file Simulate.java. It takes a two file names as a command line arguments: the file name for the precinct description and the file name for the experimental parameters. It then uses your function to determine the appropriate number of machines for that precinct. Note, the maximum number of machines it will consider is bounded by ten percent of the number of votes.
We have supplied a collection of test cases in the directory
tests.
Submission:
Check your code into gforge using the command:
We strongly recommend that you check your code into gforge at regular intervals!svn ci