COM 1204 Summer 2002, Project List

Professor Futrelle

Version of 6/23/02

Link to the main Projects page.


Symbolic computation Mondays 4pm
A simple example of symbolic computations would be to process the input string, "(x + a)(x +b)" to produce x^2 + (a + b)x + ab". A more interesting example would be to take the expression x^2 + 3x and produce its derivative with respect x which is, 2x + 3. Breadth: History of this area; current systems.

Chat System Mondays 4:15pm
Use RMI to develop a simple chat system. At first it could function as a simple peer to peer system involving only a pair of chatters at a time. It could then be extended to handle various types of group chats. Breadth: Studies of communication such as this using computers (human-computer interaction research)

Browser -- web client Mondays 4:30pm
A simple web browser that connects to a server, e.g., Apache, and does simple rendering of plain text and very simple html pages. Breadth: History of the WWW and origin of browsers. Extras: Get active clickable links working.

Relational database Mondays 4:45pm
Relational databases are normally laid out as records, each consisting of fields of fixed lengths. Then it is possible to access the n-th record simply by doing random file access at position n x recordLength. Develop simple query and update (alter and add) capabilities. Breadth: Why did relational databases win out?

UNIX shell Mondays 5pm
This would allow you to type in commands and have them executed in the underlying system, e.g., ls, cat and more. Breadth: How did shells arise to talk to an OS?

Your own Javadoc system Mondays 5:15pm
A simple system that would scan source code and generate an html page showing the class and method names. Breadth: History of automated program documentation, or alternatively, the state of text summarization in general (e.g., MIT Press book on automated summarization).

A board game Mondays 5:30pm
Checkers -- can be done on a simple grid with no graphics. Allow only legal moves. Extras: Automate one player. Breadth: History of automated game playing, especially Samuels' checker-player.

Regular expresssion matcher Mondays 5:45pm
Allow wild-card searches of various types, similar to grep. Breadth: Relation of regular expressions to regular languages and finite-state automata.

Document searcher Mondays 6pm
Build an index for a set of documents and use it to build a fast search algorithm. Allow boolean searches. Wild cards not required. Breadth: Document indexing and searching strategies used today, esp. on the WWW.

A directory viewer Mondays 6:15pm
Will list files and directories, sorted by name, date, extension (type), etc. Will open a simple text file and display in a window. Breadth: Describe visualization techniques for file systems and more.

Spell checker Tuesdays 4pm
Compare text against a dictionary list. Then, make suggestions, e.g., that "compter" should be "computer", "teh" should be "the", etc. Allow user to add entries. Dictionary must be stored on disk (serialized hash tables OK). Goal: Fast checking. Breadth: History of spelling (not spell checking) in English.

HTML viewer Tuesdays 4:15pm
Instead of a simple browser, create a more substantial viewer of HTML documents, one that can handle many different types of tags, such as <center>, <h2>, <pre>. No network connection or server needed. Breadth: Uses of XML for chemistry, math, graphics (SVG).

Natural language generator Tuesdays 4:30pm
A generator is given data can produces some type of a readable output. The generator should produce a natural language description of data. An example would be the following: A weather data file might include "Boston Wednesday 62 75". Your generator would turn that into the statement: "In Boston, on Wednesday, the low will be 62 and the high will be 75 ". Any sort of condensed concise data could be used as input to a generator. The data could be baseball statistics, a highly condensed list of medical symptoms, a list of cities and their populations, and much much more. I leave it to your imagination. Look around and you'll find lots of examples of such data. Breadth: Current work on natural language generation.

Word processor Tuesdays 4:45pm
Provides, at a minimum, italics and bold. Output in RTF and then view in Word or via Java's RTF capabilities. Breadth: Origin of the word processor.

Spreadsheet Tuesdays 5pm
Allow simple formula such as computing the total of rows in one column, or a column that is the total of the rows in all columns to its left. Breadth: Invention of the spreadsheet.

Catalog of CDs, DVDs Tuesdays 5:15pm
Build a catalog system to search and update information on CDs or DVDs. Breadth: The Dublin Core -- what is it; how is it relevant?

Diff Tuesdays 5:30pm
Build a diff utility that prints out only the differences between two files. (Harder than you think) Breadth: Bilingual text alignment is similar and useful (Canadian hansards).

Programming language interpreter Tuesdays 5:45pm
A programming language interpreter takes as input a statement or even a full program in a particular programming language and executes it to produce results. A simple example might be an interpreter for the language Scheme. If the interpreter was given the expression "(+ 3 5)" it should return 8 as the result. The interpreter would just use the Java '+' function to do the addition. Breadth: History of interpreters; discussions of interpretation versus compilation.

Number format conversion Tuesdays 6pm
Binary, octal, decimal and hex interconversions. Also, Roman numerals and English forms, e.g., "two-thousand-four-hundred-and-thirty-one". Breadth: Early history of number systems; early non-binary computers.

Multiple precision arithmetic Wednesdays 4pm
A package that can handle integers to many places, e.g., 100 decimal places. Uses Java ints as its basis. (Test correctness by comparing with Java BigInt computations.) Build on this to do the same for floats. Breadth: Actual uses of these super-precision capabilities.

Date and time computations Wednesdays 4:15pm
System that can produce a calendar for any month in any year (Gregorian calendar). Can find the difference in days between any two dates. Breadth: Precise times and leap-seconds. The Julian calendar.

Implement a hash table Wednesdays 4:30pm
Implement hashing and use it in an application such as simple spell-checking. Tricky problem: How to hash an object reference. Breadth: History of hashing; hashing techniques.

Iterator Wednesdays 4:45pm
Build a collection and iterator class from scratch and use them in an application.

Serialization Wednesdays 5pm
Using reflection, produce a simple, limited depth serialize/deserializer. Breadth: How object-databases represent objects.

Generate postscript Wednesdays 5:15pm
Given some HTML text, generate a Postscript file that can be printed, and/or distilled to PDF and viewed. Alternatively, generate a PDF file that can be viewed in the Acrobat Reader. Breadth: Early languages, such as dvi that allowed typographically faithful rendering; history of electronic typesetting.

Parsers Wednesdays 5:45pm
A parser is typically applied to text to analyze its structure. Analyzing the full complexity of English is extremely difficult. A more practical application might be to parse some XML or HTML to identify various structures in it. An example would be finding text between bold tags or header tags. More specifically, it finds enclosing structure such as paragraphs and then finds other structures contained within them, building a tree representation. To parse the text must first be tokenized into individual units. Breadth: Some of the basics of parsing theory.

Compression Wednesdays 6pm
Implement text compression/decompression using Huffman encoding. Implement a simple image compressor, using run-length encoding for a binary image. Breadth: Compression and its relation to encryption.

Output to a window Thursdays 4pm
Build a system that anyone can use so that output of their program can be sent to a window as it occurs. Breadth: Program tracing systems.

Telphone system Thursdays 4:15pm
Simulate a dialable wired phone system with a single central switch. Use threads. Breadth: History of the transition to automated dial systems.

Simulate auto traffic Thursdays 4:30pm
Simulate traffic flow at an intersection with a stoplight. "Generate" cars at a distance, headed toward the intersection. Use threads. Breadth: Simulation use in road design and/or the Simula language.

Mapquest - route planner Thursdays 4:45pm
Make a simple database about locations and routes. Then write a system that finds the shortest or fastest route, obeying one-way street restrictions. Breadth: Route planning algorithms and search.

Machine learning Thursdays 5pm
Given a list of movies or albums or restaurants, each with properties and a rating, find a decision tree that predicts the rating of a new, unrated entry. Breadth: Uses of decision trees in medicine.

Clustering for data mining Thursdays 5:15pm
Given a list, similar to the one used in machine learning, but without a rating, group the items into similar classes. Use hierarchical, bottom-up clustering. Breadth: Current techniques for data mining.

Solving word problems Thursdays 5:30pm
A system to do a few classes of word problems such as: "Jane has three eggs and Ming has four. Jane gives two to Ming. How many does each have then?" Breadth: History of automation of word problems (AI).

Matlab Thursdays 5:45pm
Pick a couple of commonly used facilities in Matlab and build a system that does them, to some approximation. Breadth: Visit Mathworks in Natick to find out about the history of Matlab and write it up.

Plotter of data graphs Thursdays 6pm
Build a plotter of data graphs that can come up with value points for the two axes and a set of points or lines or curves showing the data. Breadth: Early electromechanical plotters of temperature, pressure, earthquakes, etc.

Program that can be run backwards Thursdays 6:15pm
Build tools that a programmer can use that will capture the sequence of variable changes and function calls when code runs so that a user can "back up" through the program. Keep track of the points at which the operations are being reported. Great for understanding bugs. Extra: Scroll the source to show the point at which each change occurs. Breadth: Other work on this topic, e.g., ZStep.

Return to the COM1204 home page