CS 111: Introduction to Computer Science

Final project

Due: 5:00PM Monday, March 14. Submit in a folder called "final".

You may work alone or with one other person from the class.

Choice #1: A game

Write a game program that is enjoyable to play.

There are lots of ways to approach this problem. You can choose an asymmetrical two-person game like Mastermind, where the computer doesn't have to be too bright, but the game is still fun for the person playing it.

Given the experiences you have had this term with graphics, you could also try a one-person graphical game like Tetris or minesweeper. For games of that sort, you'll probably need to give the user a way to use the keyboard and the mouse in interaction with a graphics window. The sample programs clickablewindow.py, typeablewindow.py, and twowindows.py should help you get started.

Alternatively, you could pick a game that requires a smart computer. For example, making the computer play tic-tac-toe (2D or 3D) or Bagels or dots-and-boxes intelligently is an interesting problem. You could even take a harder game like Boggle, and make the computer generate a random Boggle board and then search the board for words and print them all out. In the end, the approaches can be: make the game fun, make the computer smart, or both.

You only have two weeks, and you have an exam in the meantime, so pick a game that's simple enough that you can get the job done in time. Tic-tac-toe is simple enough, but Hearts probably is not. A simple text adventure (like Zork, if you've ever heard of it) is manageable. Chess is not.

If you want some more ideas of appropriate games, let me know.

Choice #2: A graphical simulation

One of the things computers are good at is simulation of systems that evolve over time. Consider, for example, a computer model of the solar system. You can give the computer the initial positions, masses, and velocities of the largest objects in the solar system, plus a computational mechanism for simulating the effects of Newton's law of gravitation. Then you can set the system running, and your solar system will go through its motions. You could then try adding a comet with a mouse click or two, and watch how the comet's orbit is perturbed by close encounters with planets or asteroids. If the simulation takes relevant physical laws into account, the evolution of the system will be a good representation of the workings of the real solar system.

If you choose this project, you will simulate some time-dependent system that can be represented effectively in a rectangular display. You could show a top view of the solar system, or a side view of an aquarium, or a landscape with rain, clouds, plants, and birds. Your system will need to be animated, and there will need to be a diverse enough collection of elements to your system that the objects will have interactions of some kind. Planets, for example, interact gravitationally, big fish eat little fish, and raindrops cause plants to grow.

Your simulation may include pretty much any features you can cook up, but its minimal features must include:

More than one type of moving object.
Interactions between objects.
Some feature that allows either mouse-clicks or keystrokes to affect the simulation in some way (click to create a plant, or hit the "+" key to speed up the simulation, or click on a fish to see a window pop up containing the fish's vital statistics, etc.)

Choice #3: A function-grapher with Monte Carlo integration

This is one of my old favorites, and I offer it as an option for the calculus fans out there.

Suppose you want to approximate the area under the graph of a function. You may have seen techniques like the trapezoidal rule or Simpson's rule, but there's another technique called Monte Carlo Integration. Take, for example, the graph of f(x) = x**2 between x=0 and x=2 (where ** means exponentiation). The graph fits inside the rectangle R = [0,2]x[0,4]. Now suppose you generate a few thousand random points in R. If you compute:

 # of points under the graph of f
___________________________________

       total # of points

and then multiply this ratio times 8 (the area of R), you'll get an approximation of the area under the graph of f.

For this project, you will write a program that graphs functions provided by the user, and computes Monte Carlo approximations of their integrals.

Your program should ask the user to specify a function and its bounding rectangle (your program does not have to figure out the y interval from a given x interval--that's a hard problem). The user should also be able to choose how many random points your program will generate. Once the user has ordered up an approximation, your program should do two things:

Open a graphics window, draw the graph of the function, and draw the random points, and
Print next to the graph a summary of the integration computation: the number of points generated, the number of points falling below the graph, the area of R, and the resulting approximation of the area beneath the graph of the function.

If this project strikes your fancy, then you'll definitely want to test your program with math.sqrt(4-x**2) as one of your functions.

The Python "exec" function is a handy tool for this program. It allows you to create a string variable containing Python code, and then execute it. Suppose, for example, that the user responded to the raw_input below by typing "x**2 - 2*x + 1".

s = raw_input('Type a function with variable x: ')
x = 4
exec('print ' + s)

Then the output of this code fragment would be "9".

Choice #4: Your own idea

Have a good idea of your own? Talk to me about it.

Grading criteria

Does it run? If it doesn't, I can't test it, and thus I can't grade it.
Does it work correctly? Correctness is the most important thing, though by no means the only thing. Your program should work. If it doesn't do exactly what it was intended to do, you should provide a discussion of that fact in your documentation.
Is it well organized? We have talked about principles to use when designing a class, splitting problems into functions, etc. Think about those ideas as you develop your code.
Is it well documented? Your code is a piece of writing directed to two audiences--human readers and the Python interpreter. You need to make the code readable to both of them, and clear commenting is an essential part of what you do for your human readers.
Is it written with good style? Descriptive variable/function/parameter names, consistent indentation and placement of braces, and appropriate comments are the fundamentals of good coding style.
Ambition. If two projects are well documented, functional, and exhibit good style, the one that does a more interesting or ambitious thing is likely to get the better grade. A good version of Battleship will probably get a better grade than a good version of tic-tac-toe. On the other hand, a really outstanding tic-tac-toe program can certainly get an A.

What to hand in

By 11:59PM Wednesday, March 2: send me an e-mail briefly describing your project. Include an incremental development plan, as discussed in class on Feb 25.

By 5:00PM Monday, March 15: Hand in your source code and any other files your program needs. Also hand in a file called readme.txt, containing a summary of the status of your program. Tell me what your program does, what isn't working, how to use it, what bugs you know of, etc. Anything you want me to know about your program should go in readme.txt.

Put all of your files into a folder called "final", and submit it in the usual way to your hand-in folder. If you need to submit one or more revisions, call them "final2", "final3", etc. so I'll know which one to grade.

Have fun

And have a great break, too.