Boggle is a great game involving the search for words in a 4x4 grid of letters. If you want to see it in person, come visit my office.
If you choose to do this project, you will write a version of Boggle intended for play in a terminal window. The goal will be to write a game that is fun to play. Thus, you need to pay careful attention to making your user interface good.
I don't see a non-networked way to make a computer version of Boggle effective as a two-player game, so you should focus on making it fun as a sort of solitaire challenge. Your program should definitely make a complete list of words in the grid available to the player, but perhaps only after a time-limit has expired.
To write a terminal-based user interface, the best and most portable tool is the curses library. Implemented originally for C, there are also curses libraries for Perl and Python.
Here are a few tools for you. There is a good list of 2-to-8-letter words in /Accounts/courses/cs257/words.txt. Also, I have prepared a 2D array of letters representing the actual Boggle dice. And finally, go to the Example programs page to see a curses example.
For the first year of the new project-based CS comps, Dave and I directed the CS majors to this sign-up form, which sends information to me via e-mail. Once the students had all entered their preferences in this way, we put together teams manually. We tried to optimize according to the students' rankings of the topics, with reasonable success, but the process of matching students to topics was difficult.
For this project, I want you to design and implement your own system for collecting preferences from students and producing team assignments based on various criteria. You will need to create a sign-up form that collects from the students whatever data you deem relevant, and an administrative form from which the professors can specify parameters and generate possible matchings.
This is a tricky design problem. It is not immediately obvious what data we should be collecting from the students, nor is it obvious on what criteria we should try to optimize the team assignments. Some things are clear (for example, teams should have at least three or maybe four people), but others are not (is it more important to get your preferred topic, or your preferred teammates?).
This is also a tricky algorithms problem. Even if you have chosen your optimization criteria (for example, have at least four students per team, and minimize the sum of the squares of the ranks the students gave to their assigned topics), solving the problem exactly may be intractable. If there are 20 students and four topics, a mindless brute force approach to finding optimal solutions might go through 4^20 cases. In the general area of matching, there are many NP-complete problems. Thus, you may need to get clever about which cases to consider.
You will probably want to use a MySQL database for this project. If you don't already have a MySQL password, talk to Mike.
If you have never used lynx, you ought to try. Open a terminal window and type "lynx http://www.mathcs.carleton.edu/" and see what happens.
For this project, you will write a limited curses-based web browser. In one sense, the interface design won't be too hard, since you have lynx as a model. But there is no reason to follow the lynx approach religiously if you see room for interface improvement.
So which HTML tags should you recognize? At minimum, you should do sensible things with <p>, <h1>-<h7>, <ul>, <ol>, <li>, <br>, <hr>, <a>, and <b>. But I also want you to handle the <form> and <input> tags sufficiently to deal appropriately with simple text fields and submit buttons. Of course, if you want to do more, there are many tags (tables? drop-down lists?) to keep you busy.
For the tags listed in the previous paragraph, I do not expect you to implement the full power of each tag--just take care of the most basic cases. For example, make your <a> tag implementation take care of href links to other pages, but don't worry about named anchors, mailto URLs, etc.
If you were writing a browser for serious use, you would want to interact with web servers using some sort of TCP interface (sockets, streams, etc.). For this project, however, I suggest that you exploit the many wonderful features of either wget or curl, both of which are installed on our Linux systems.
Hand in the following (in a directory named "final") via HSP by 5:00PM Monday, June 9, 2003.
Source code
A text file called readme.txt containing a discussion of the status of your program, and a description of the tests you ran on your project.
Anything else you consider relevant, including Makefiles, use cases or diagrams (only if you created them for your own benefit), data files, usage statements, compilation instructions, etc.
Correctness. If you implement a feature, make sure it works correctly. Think about how you're going to test your features before you start coding. You might even go so far as to write a collection of test cases and/or a unit testing plan before doing anything else.
Style. Appropriate commenting, indentation, naming, use of symbolic constants, etc.
Modularity. I expect you to make good use of the data abstraction tools available in your language(s). All of these projects will benefit from object-oriented design. Even a straight C implementation should be using well-chosen structs and functions.
Appropriate use of libraries. Don't write your own versions of isalpha and strcpy. Make a point of knowing (or asking about) your language's standard libraries.
Portability. Curses programs should compile and run on just about any Unix, including Linux, MacOS X, and Cygwin.
Assertions. Enforce your pre-conditions with assertions.
User interface. Make your program pleasant and efficient to use.
Performance. This is probably only relevant for project #2, but don't make me wait too long for the program to respond.
Good memory management. Putting your new/delete pairs in appropriate places, doing dynamic memory allocation instead of imposing artificial limits on the sizes of things, etc.
Start early, have fun, and keep in touch.
Have a great summer and beyond.