CS 117 Final Project
Due 5:00PM, June 4, 1996
Hand all documents in via HSP
The Project
For your final project, you will write a simulation program.
The goal of a simulation program is to answer
interesting questions about the thing being simulated.
Here are some examples of simulation scenarios.
- I want to know by which route I should cross Highway 3
when I drive from home to Carleton. Should I go down 2nd
street and cross at the Hwy 3/2nd St. light, or should I
go down St. Olaf Avenue, turn right onto 3, and then turn
left at the 2nd St. light? Does the time of day matter?
How does the fact that the intersection has hardware that
allows it to detect the presence of cars affect my decision?
- I want to know the frequency with which the squares
on a Monopoly board get landed on during a typical game.
- I own a grocery store with one checkout counter, and I want to
know the average time my customers have to wait in line
before being served, and what percentage of the time
my checkout clerks are idle. To simulate this situation,
I will need to make assumptions about the average
frequency with which customers arrive at the checkout
counter, and the average length of time it takes to
serve a customer. How are the wait and idle times
affected by these assumptions?
- I own a bigger grocery store, and I want to know how many
checkout lanes I should have, and how many of those
should be express lanes. I want my clerks working as much
of the time as possible, but I also want the customers'
wait to be relatively short. How are my lane decisions
affected by various assumptions
about the frequency with which customers become ready
to check out, the sizes of their loads, etc.
- Consider the mindless Tic-Tac-Toe strategy of picking
a square at random whenever it's your turn. Contrast
this with the strategy of always blocking your opponent
if necessary, and otherwise picking your square at random.
It's clear that the second strategy is superior, but
by how much? What percentage of games will the completely random
strategy win? Similar questions, of course, can be asked
about other strategies and other games.
- My uncle has a betting method which he claims won
him a lot of money at Roulette during the Korean War. I have
always believed that his method was flawed, but I haven't
sat down to prove I'm right. To get some confidence, I'd
like to write a simulation of Uncle Kingsley using his method
over a large number of Roulette sessions. The question
I want to answer is this: what are Kingsley's average
winnings? (I bet they'll be negative.) If you're interested
in UK's method, let me know, and I'll explain it to you.
- I like calculus. I have always liked integration, which
lets you compute areas under curves. There's a method for
approximating integrals called "Monte Carlo integration"
that is a simulation of sorts, and appropriate for this
assignment. To compute the integral of x^2 over the
interval [0,2], for example, I would generate a bunch
of random points in the rectangle [0,2]x[0,4]. I would
divide the number of these points that fell below the
y = x^2 curve by the total number of points to get an
approximation of the fraction of the area of the
rectangle that falls below the curve. Here are some questions
to ask. For a variety of test functions, how many random
points do you need to generate to get reasonable estimates
of the functions' integrals? Can you use Monte Carlo
integration to estimate the value of pi? Can you use
Monte Carlo methods on 2-variable functions? How does
Monte Carlo compare with the trapezoid rule, or Simpson's
rule?
The Schedule
The following are due by Wednesday, May 29. Send them
to me by e-mail at jondich.
- A description of the scenario you intend to simulate.
- A list of questions you hope to answer using your simulation.
- A description of the smallest time unit your simulation
will use, and what events will occur during each
time unit.
- A list of the intermediate versions of the program
you intend to implement. These versions should start very
simply, and increase in complexity.
Due noon Tuesday, June 4, via HSP
- Your fully commented source code
- Your scenario description and list of questions,
as in the May 24th portion of the assignment.
- A description of the status of your program (what works,
what doesn't, etc.).
- The data you collected with your program and a
discussion of your results.
Grading criteria
- You must meet the deadlines listed above.
- Your final program must compile and run. If it does
not compile, I won't grade it at all. If it compiles,
but crashes a lot, you will get a low grade. I would
much rather see a functioning program that does not
do everything than a program that tries to do everything
but does none of it successfully.
- An A program will model an interesting scenario, and
produce data that helps answer interesting questions about
the scenario. An A project requires
well-documented and easy-to-read code, as well as a good
discussion of the results of the simulation.
An A program needs
to show some ambition, as well as good execution.
A C program will compile, run, and produce data more
or less relevant to the scenario in question.
A C project will include a discussion of the scenario
being simulated and the questions the program was intended
to answer.
A little advice
Don't start late.
Have a careful plan of the small steps you will take in travelling
from no program to the final program. Design your program
modularly, so you can make the modules work one at a time.
Don't go to sleep without a program that compiles and runs without
crashing. It doesn't have do anything--just don't try to do so
much at once that you can't wrap up the day's work into a running,
partially complete, program.
Make copies of your program before making changes.
Don't assume that a simple simulation can't yield interesting
results or answer interesting questions. Build up your
simulation in small steps, answering your major questions
first for an simple model of the thing you are simulating.
Then add extra wrinkles to your simulation and answer the
questions again. Repeat until you are satisfied with
your model.
Make sure to give yourself enough time at the end of the
process to collect, present, and interpret your data.
Miscellaneous
Feel free to talk to each other and learn from each other, and compare
approaches to the problems posed by these programs. I ask, however,
that all your code be your own. If you take a significant idea from
another person, please give explicit credit to that person.
Talk to me. I will hold regular office hours
during reading and exam days. I will post my hours on my office door.
Start early, keep in touch, and have fun.
Jeff Ondich,
Department of Mathematics and Computer Science,
Carleton College, Northfield, MN
55057
(507) 663-4364,
jondich@carleton.edu