CS 117 Final Project
Due 5:00 PM Monday, 11/22/99
For your final project, you will write one of the four programs
described below. You will work alone for this project. This does
not mean that you shouldn't talk with each other and lab assistants
about your project. It does mean that the bulk of your code should
be your own, and that any assistance you receive from others
should be acknowledged in the comments and documentation accompanying
your code.
I: Spell-checker
If you choose this project, you will write a simple spell-checker.
Your program should prompt the user for the name of a dictionary
file and the name of a text file to be checked for spelling errors.
For each word in the text file that is not found in the dictionary
file, your program should print out the word itself plus the number
of the line on which the word appears.
You may assume that the dictionary file consists of one word
per line, sorted alphabetically.
For this program, you should probably implement a
Dictionary class of some kind. An example Dictionary
class is described in
dictionary.h , but you
may modify it or design your own from scratch.
You can test your program with any sort of made-up dictionary file,
but will find a pretty good dictionary file
in /Accounts/courses/cs117/ondich/words.txt,
in case you want a realistic one. This file contains about 80,000
words, one per line, and is about 600Kb long, so you'll need to
think about how to handle such a big database if you want to
use this dictionary file.
II: Moveable Movies
If you choose to do this project, you will write a program that
uses the
g2 graphics library (here's an
example graphics program )
to display a short movie.
The content of your movie is up to you, but it
need not be complicated (in fact, you should probably avoid excessive
complication so as to preserve your finals week sanity).
There's a catch, though. Your code must be organized so that
the movie can be shown in a frame of any size or location. In particular,
your code should include a function described as follows:
//
// DrawFrame
//
// Draws the Nth frame of the movie inside the rectangle
// the coordinates of whose top, bottom, and sides are
// given by the parameters top, right, bottom, and left.
// Note that no drawing is done outside this rectangle,
// and that no assumptions are made about the width, height,
// or ratio of width to height of the rectangle.
//
void DrawFrame( int N, int bottom, int left, int top, int right );
There are lots of cute tricks you can play with your movie if you
organize the code in this way. For example, you could show the
movie in two locations on the screen simultaneously by doing
something like this:
for( int i=0; i < nFrames; i++ )
{
DrawFrame( i, 0, 0, 200, 200 );
DrawFrame( i, 300, 300, 500, 500 );
}
Or you might show all the frames simultaneously in one window, lined
up in a grid so you could compare all the frames at the same time.
Or you could draw a fancy border, and show the movie inside it.
You need not do any of these things with your code, but you should
definitely test it in rectangles of various shapes and positions.
NOTE: DrawFrame should not call g2_open_X11(). In fact, your main
program should call g2_open_X11() once, after which g2_open_X11() should
never be called again.
III: Anagrams
An anagram of a word or phrase is a word or phrase that
can be formed by rearranging the letters in the original word or phrase.
For example, "dear" is an anagram of "read," "twelve plus one" is an
anagram of "eleven plus two," and "Fjord Conifer Thereby" is an
anagram of "Jeffrey Robert Ondich." There are more where those came
from.
For this project, you will write a program that gets a word or phrase
from the user and prints out a list of anagrams. You may use
the dictionary file /Accounts/courses/cs117/ondich/words.txt to provide
data for your anagram hunt. Also, you may restrict your anagram
search to single words rather than words and phrases.
Anagram finding is pretty tricky, and there
are lots of ways to approach it, but let me
give you one idea. You can compute something we'll call the
"signature" of a word (or phrase, for that matter) by making an
alphabetical list of the letters in the word. Thus, for example,
the words "dear" and "read" both have the signature "ader." Perhaps
you can put the signature idea to use.
IV: Monte Carlo Integration
This one is most likely to make sense to you if you've taken calculus.
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. 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, write a program that will compute Monte Carlo
approximations of integrals. Your program should present the
user with a menu of three or four functions to choose from,
and should ask the user to specify the rectangle R (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 to cout 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 use sqrt(4-x^2) as one of your functions.
What to Hand In, When, and How?
- By 5:00 PM, Wednesday, November 17 (the last day of classes),
send me the following via e-mail at
jondich@carleton.edu:
- An explanation of which project you plan to do.
- Declarations of any major classes your program will use (if any),
and prototypes of the major functions in your program.
The functional prototypes should include comments explaining
what the functions will do.
- A pseudo-code version of your main program, with comments.
- A brief plan of attack--the order in which you plan to
implement your project's features, etc.
The more design detail your provide in this e-mail, the better
feedback I'll be able to give you. You can send me this e-mail any
time before the 17th, and I'll reply by e-mail within 24 hours.
- By 5:00 PM, Monday, November 22, submit the following via
HSP:
- All your source files, both .h and .cpp, as appropriate.
- A file named finalReadMe.txt, which should include a
list of the source files in your project, a description of
what your program does, and a description of the status of
your program (what works, what doesn't, lingering bugs, etc.).
Grading Criteria
- Does your program compile? I can't test it (and thus can't grade it)
if it doesn't compile. Note that many people add their comments
only after they have completed their coding. This is a very bad idea
from the software design point of view, but it is also a great
way to accidentally introduce syntax errors. Always compile and
run your program immediately before submitting it.
- Does it work? 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 your program's limitations in your documentation.
- Is your program well organized?
Well-designed function interfaces, good use of classes where
appropriate, and a main program that reads like an outline of the
program as a whole contribute to readable, debuggable, and maintainable
programs.
- Is your program well documented? Your code is a
piece of writing directed to two audiences--compilers and human readers.
You need to make the code readable to both audiences,
and clear commenting is an essential part of what you do for your
human readers.
- Is your program 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.
- Sometimes, efficiency is relevant. For example, a bad
search algorithm with a big dictionary can lead to
unreasonably long run times for a spell-checker.
- If everything above is done well, an ambitious program
may get a better grade than a less ambitious one. For example,
a spell-checker that can handle an arbitrarily large dictionary
is more impressive than one that can handle only 200-word dictionaries.
On the other hand, a 200-word spell-checker that is works correctly and is
well organized, designed, and documented is much better than a
buggy, messy, poorly commented spell-checker that can use a big dictionary.
That's all
If you have questions, please let me know.
Start early, stay in touch, and have fun.
Jeff Ondich,
Department of Mathematics and Computer Science,
Carleton College, Northfield, MN
55057, (507) 646-4364,
jondich@carleton.edu