CS 111: Introduction to Computer Science

Final Project

Hand in final code and documentation by 5:00PM Monday, June 8

Your final project will consist of a folder containing your entire program. You should hand it in using the usual process. Please name your project "final".

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

Choice #1: Game

Write a game program.

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 function-grapher with Monte Carlo integration

Though I imagine most of you will go for a game of some sort, 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".

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 5:00PM Monday, June 8: 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 summer, too.