11/3/2019 1/13 Polling places You may work alone or in a pair on this assignment. Every two years, many people around the country wait in long lines to vote due, in part, to inadequate provisioning of...

11/3/2019
1/13
Polling places
You may work alone or in a pair on this assignment.
Every two years, many people around the country wait in long
lines to vote due, in part, to inadequate provisioning of voting
ooths. In this assignment you will write code to simulate the
flow of voters through precincts. The information generated by
your simulator could be used by an election official as a crude
lower bound to help determine the number of voting booths need-
ed at a precinct.
We will view this problem as an instance of the more general
problem of simulating an / / queue, where:
the first indicates that a
ivals (voters a
iving at the polls) obey a Markov process;
the second indicates that the service times obey a Markov process (the amount of time a voter takes
to complete a ballot); and finally
the indicates that there are servers (the number of voting booths).
We will tell you how to structure your implementation at a high level, but you will be responsible for the
design details.
Getting started
See these start-up instructions if you intend to work alone.
See these start-up instructions if you intend to work with the same partner as in a previous assignment.
See these start-up instructions if you intend to work in a NEW pair.
The pa4 directory includes a file named simulate.py, which you will modify, a file named util.py that
contains a few useful functions, a directory named data, which contains precint configuration files (de-
scribed below), and a series of tests contained in files test_avg_wait_time.py,
test_simulate_election_day.py and test_find_number_of_booths.py.
Please put all of your code for this assignment in simulate.py. Do not edit other files or add extra files fo
the required classes.
Precinct Configuration
The configuration for a precinct is specified using a dictionary containing this information:
The name of the precinct (name)
number of voters assigned to the precinct (num_voters),
number of hours the polls are open (hours_open),
The number of voting booths (num_booths)
The voter distribution (voter_distribution).
For example:
{'name': 'Downtown',
'num_voters': 5,
'hours_open': 1,
'num_booths': 1,
'voter_distribution': {'type': 'poisson',
'a
ival_rate': 0.11,
'voting_duration_rate': 0.1}
M M N
M
M
N N
https:
www.classes.cs.uchicago.edu/archive/2019/fall/30121-1/_images/voting_booths.png
11/3/2019
2/13
Notice how the voter_distribution field contains another dictionary containing these fields:
The type of distribution (type). In this assignment, we will only deal with one type of distribution:
poisson
The rate at which voters a
ive (a
ival_rate) and the rate at which voters complete their voting
(voting_duration_rate). The significance of these rates is explained later.
Information about precincts is stored in a JSON file that contains a dictionary with two keys: precincts,
containing a list of precinct configurations as specified above, and seed, containing a random seed. Simila
to PA1, the random seed will be used to ensure that a simulation involving randomness produces the same
esult (which will allow us to test whether your code produces the expected results). We recommend re-
viewing PA1 (and how it used random seeds) if you’re unsure of how random seeds are used in the context
of running a simulation.
We have provided a function, load_precincts in util.py that takes the name of a JSON precincts file
and returns two values: a list of precinct configurations (as specified above) and the random seed.
This function is already called from the code we provide for you, so you should not make any calls to
load_precincts in the code you’ll add to simulate.py. However, it can be a useful function when testing
your code. In particular, you should take a moment to familiarize yourself with the data stored in these
JSON files, and how to access each value once you’ve loaded the file with load_precincts. We suggest
you start by looking at data/config-single-precinct-0.json, and loading that file from IPython:
Representing Voters
In this assignment you will need to model voters using a Voter class. This class must include the time the
voter a
ives at the polls, voting duration, that is, the amount of time the voter takes to vote, and the time
the voter is assigned to a voting booth (aka, the start time). For simplicity, we will model time as a floating
point number, representing the number of minutes since the polls opened. So, if we say a voter a
ived at
the polls at time 60.5, that means they a
ived an hour and thirty seconds after the polls opened.
While not strictly necessary, we found it convenient for debugging purposes to store the time the vote
leaves the voting booth (i.e., the departure time) as well.
In [1]: import util

In [2]: precincts, seed = util.load_precincts("data/config-single-precinct-0.json")

In [3]: precincts
Out[3]:
[{'hours_open': 1,
'name': 'Downtown',
'num_booths': 1,
'num_voters': 5,
'voter_distribution': {'a
ival_rate': 0.11,
'type': 'poisson',
'voting_duration_rate': 0.1}}]

In [4]: seed
Out[4]: XXXXXXXXXX

In [5]: len(precincts)
Out[5]: 1

In [6]: p = precincts[0]

In [7]: p["num_voters"]
Out[7]: 5

In [8]: p["voter_distribution"]["a
ival_rate"]
Out[8]: 0.11
11/3/2019
3/13
The start time for a voter, which is not available at construction time, should be initialized to None when
the voter object is constructed. This value should be reset to the co
ect value when the voter is assigned to
a voting booth. Similarly, voters’ departure times cannot be determined until we know their start times.
Your implementation must include at a minimum: a constructor and public attributes named
a
ival_time, voting_duration, and start_time. Our utility function for printing voters, described be-
low, relies on the existence of these attributes.
This class is straightforward. It merely serves as a way to encapsulate information about a voter. Our im-
plementation is roughly 10 lines.
Please note, the precinct class, described next, is the only class that is allowed to call the Vote
constructor.
Precincts
Cities are
oken up into voting precincts, and your implementation must include a Precinct class that
epresents a single precinct, and which will be responsible for simulating the behaviour of voters in that
precinct.
A precinct is open for some number of hours, and has some maximum number of voters who can vote in
the precinct (you can think of this as the number of voters who are registered to vote in that precinct). We
will assume that all registered voters will go to the polls on election day, but not all of them may get to
vote, because some could a
ive after the polls close. As we will explain later on, a precinct also has some
number of voting booths (which can affect how quickly we can process voters)
Notice how having a Precinct class allows us to have multiple Precinct objects in our program, each
with its own set of parameters. This will make it easier for us to simulate the behavior of multiple
precincts, as well as compare the effects of those parameters. For example, we could create two Precinct
objects with the exact same parameters, but where one precinct has one voting booth and the other one
has two voting booths. Simulating both can provide insights into how the number of voting booths can af-
fect waiting times.
We have already provided a skeleton for the Precinct class that includes the constructor and a simulate
method to simulate a single voting day on that precinct. While you are allowed to add additional methods
to this class, you cannot modify the parameter list of the constructor and the simulate method.
Please note that we will consider each Precinct as completely independent from each other: voters cannot
go from one precinct to another, and there is no shared information between the precincts.
Generating Voters
One of the main responsibilities of the Precinct class is to generate the voters according to some random
distribution (in our case, we will only be using a Poisson distribution), so let’s take a closer look at how
those voters will be generated.
Both the a
ival time and the voting duration of our voters will follow a Poisson process. From Wikipedia:
a Poisson process, named after the French mathematician Simeon-Denis Poisson XXXXXXXXXX), is a sto-
chastic process in which the time to the next event is independent of past events. We can use the following
fact to generate a voter sample: if the number of a
ivals in a given time interval [0,t] follows the Poisson
distribution, with mean , then the gap between a
ivals times follows the exponential distribution with
ate parameter .
This means that a Precinct object must keep track of time. We will assume that we keep track of time in
minutes starting at time zero. To generate a voter, you will need to generate an a
ival time and a voting
duration. To generate the a
ival time of the next voter, you will generate an inter-a
ival time ( ) from
the exponential distribution using the specified a
ival rate as and add it to the cu
ent time ( ). You’ll
then move time forward by updating the time from to . Notice how represents the time that
elapses between the a
ival of the previous voter and the a
ival of the next voter.
t ∗ λ
λ
gap
λ t
t t + gap gap
11/3/2019
4/13
For example, let’s say we want to generate a voter in a precinct, and the random number generator returns
5.7 for that voter’s gap. Since this is the first voter we generate, their a
ival time will be 5.7, and we ad-
vance the precinct’s cu
ent time from 0 to 5.7. We then generate another voter, and the random numbe
generator returns 2.4 for the voter’s gap. This means that this second voter a
ives 2.4 minutes after the
previous voter, so the second voter’s a
ival time will be XXXXXXXXXXand we advance the precinct’s
cu
ent time to 8.1.
When we generate a voter, we also need to assign a voting duration to that voter. You will draw the voter’s
voting duration from the exponential distribution using the specified voting duration rate as .
For testing purposes, it is important that you draw the gap and the voting duration in the same order as
our code. To reduce the likelihood that the testing process fails simply because the values were drawn in
the wrong order, we have provided a function, gen_poisson_voter_parameters, in util.py that takes
the a
ival rate and the voting duration rate as arguments and returns a pair of