CS 117 Final Project

The Project

• 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

• 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

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

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.