2009 May 22 / jj|d|a|v|i|s|@|c|a|r|l|e|t|o|n|.|e|d|u
Carleton College CS 201, Spring 2009, Prof. Joshua R. Davis
In this course there is not a final exam but rather a final project that counts for 25% of your course grade. The goal of the project is for you to complete a significant task using one or more data structures from the course — particularly trees and graphs — in depth. A rough guideline is that the project should require at least three times as much work as a typical assignment. I encourage you to work with one partner.
I give several project ideas below. Some of them require knowledge from outside courses such as physics, biology, or math. Many of the ideas are of the form "implement this data structure and then use it to do something useful". They are deliberately open-ended, so that you have room for creativity. You also have room for getting lost in too many options; to avoid getting off track, you will give Eric and I frequent progress reports.
The final product of the project will probably be some mixture of Python code and discussion/report. It is due at 11:00 AM on Saturday June 6.
A suffix tree is a data structure that enables fast searching for substrings in a given string. It is used in analysis of DNA, analysis of written texts, and compression of images.
I propose that you implement a suffix tree (or related data structure — there are many) and use it to for some interesting application related to DNA, natural language text, or images.
Mathematica and Maple are computer algebra systems — high-powered calculators that are capable of not just numerical calculation but also algebraic calculation. In our course we have studied how an algebraic expression can be represented as a tree, with operators at branch nodes and operands at leaf nodes. This core idea is all you need to write to write your own basic computer algebra system. In fact, I wrote one last year to help my calculus students practice differentiation; you can try it out yourself.
I propose that you write your own computer algebra system, capable for example of simplifying complicated expressions, expanding out complicated products, differentiating functions, etc. You can use your Interpretation assignment as a starting point.
In our Interpretation assignment we implemented a simple programming language that, while it contained the key ideas of language implementation, ended up being little more than a glorified calculator. Conspicuously missing features were:
if-then-else statements,
True or False; to implement if-then-else statements you need some sort of Boolean type, because that's what comes between the if and the then.)
I propose that you design your own programming language that includes these features and whatever else you desire. You get to design the syntax however you like (within reason). You could build on the Interpretation assignment, or you could strike out in a different direction. For example, if you require all syntax to be in prefix form, then your parser can be kept extremely simple even while you add new features to the language. It's up to you.
Conway's Game Of Life is not really a game, but it certainly is entertaining. It takes place on an infinitely large grid. Some of the grid squares are "occupied" with a creature and some are not. Over time, new occupants are born and old occupants die off according to a simple rule. Surprisingly complicated behavior emerges, such as configurations that reproduce themselves. The obvious data structure to use, for representing the grid, is a two-dimensional array — i.e. a list of lists — but it does not represent infinite grids easily, and it's too slow.
I propose that you implement a sparse matrix, customized for the Game Of Life, and then implement a simulator for the game itself using the sparse matrix and Bopa.
A road network is a graph in which the nodes are intersections and the edges are roads. At DIMACS you can download the entire road network of, say, Minnesota.
I propose that you build these data into a graph and use graph algorithms to answer interesting questions about roads. For example, you could make a trip planner with a simple graphical user interface written in Bopa.
A social network such as Facebook is a graph in which the nodes are people and the edges are friendships among those people. There are publicly available data on such social networks, for example at the INSNA.
I propose that you build these data into a graph and use graph algorithms to answer interesting questions about these social networks. For example, if someone has two friends, then what is the probability that they are friends with each other?
An electrical circuit is a graph in which the nodes are components (resistors, batteries, etc.) and the edges are wires. There are basic rules, such as Ohm's law and the Kirchhoff current law, for computing voltages, currents, etc. throughout a circuit.
I propose that you use graphs and Bopa to write a program that lets the user build a circuit and automatically compute the voltages, currents, etc.