Possible Projects

Here are some ideas for possible projects. We will add to this list as we think of more, so be sure to check again later. And of course, you are encouraged to design your own project! The possible projects are described in more detail below.

Chess Program.

Modify Larry's TicTacToe program (which we'll learn about in class on Monday) to play chess. A realistic goal is to get it to solve "White to mate in 3 moves" problems. You'll need to design a data structure for a position, build "methods" (java-speak for functions) that input and display moves and positions, and make a method that makes a list of the legal moves from a given position.

A more ambitious goal is to make the program play reasonably well even when it can't do an exhaustive search. This involves the above, plus building a method that can evaluate how good a given position is.

The first part of this project ("mate in 3" problems) shouldn't be that difficult, but at least one of the team members should have a some experience in C++ or Java, and one should know how to play the chess.

Incidentally, instead of chess, you could try another game that doesn't involve randomness, such as 3-dimensional Tic-Tac-Toe or checkers. I would rate these as "more ambitious" also, even though the rules are a little easier than for chess, because it's not obvious how to evalutate a position.

Back to the list.

Parallel sorting.

In class, we acted out three methods of sorting ourselves into alphabetical order. These were "parallel algorithms", since multiple things could be going on at the same time. Larry claims that both BubbleSort and QuickSort take time at least N to sort a list of N items, even if the computer can do N things simultaneously.

Your goal is to invent other parallel sorting algorithms, analyze approximately how long they will take (as a function of N) and ideally to find one that can run significantly faster - perhaps a constant times the square root of N. This project doesn't involve any programming (unless you want it to), nor do you need to know much of anything about ordinary sequential sorting algorithms. But it's a not an easy problem.

Back to the list.

Study freeway driving.

By Monday, Larry hopes that a freeway simulator will be working. (Unfortunately, it may never be very good, so don't get your hopes set on this project). The simulator will let you define a bunch of different types of drivers and automobiles, and let them loose on a simulated freeway. Your goal is to investigate (using the scientific method!) what driving styles are safer than others. For instance, one hypothesis is that if everyone drives the same way, then it's a lot safer than if different people have different driving habits. A different hypothesis is that the most important thing is not to tailgate.

No programming is required. It might help if at least one team member knows how to drive.

Back to the list.

Understanding machine code.

When you compile a program, the compiler translates your C or C++ program into the much more primitive machine instructions that the computer actually executes. The goal of this project is to gain some understanding of what the machine instructions actually do, and perhaps a little insight into, for instance, seeing what happens when you tell the compiler to "optimize" your program.

Although you don't need to know anything about programming or how computers work to do this project, you shouldn't attempt it unless you really really like understanding low-level details. But if you do, you can learn a lot about how computers really work.

Back to the list.

Build a physics simulator.

We played with a bunch of these in the lab. The goal of the project is to build one yourself. Some possible ideas are to simulate the motion of a drum head or of an ocean wave. *Warning!* You need a very experienced programmer on the team to pull this off.

Back to the list.

L-Systems and Fractal Growth

Structures in natural systems (plant growth, animal circulatory systems, etc.) often reflect fractal geometries. These fractals in biological systems must be grown, and the "programs" are found in DNA. In this project, you will investigate some of the formalisms and programs for the fractals. You will do some research on L-systems (named after Aristid Lendenmayer who invented the formalism in 1968), and explore various known programs. You will also try to develop your own programs. The fun part is seeing what the fractals produce. Note that this does not require prior knowledge of any "programming language" - anyone can learn this from scratch. Most of the research can be done using the Web and the library.

Back to the list.

Cellular Automata

A cellular automaton (CA) is a type of computing machine invented by John von Neumann, one of the fathers of computer science. A CA is defined by a grid (it could be one-dimensional, or two, or more), with each element of the grid being "on" or "off", and a set of rules that describe how each element changes based on the states of neighboring elements. Despite this simple description, CAs are capable of a wide range of behavior, and capable of universal computation (i.e., as "powerful" as any computer). In this project, you will explore the various types of CAs and their behaviors. This project does not require prior knowledge of any programming language - anyone can learn this from scratch. Most of the research can be done using the Web and the library.

Back to the list.

Autonomous Agents

An autonomous agent (AA) is a simple entity that interacts with its environment and other AAs, typically based on a simple set of rules. For example, the AAs may be birds that randomly fly around a grid, but obey simple rules like avoiding bumping into each other and not flying directly behind another bird (otherwise it cannot see). It is interesting to then observe the "emergent behavior," such as the patterns of movement. Researchers have developed very simple rules that seem to mimic the patterns seen in nature of how birds fly in formations. In this project, you will explore the various types of AAs and their behaviors. This project does not require prior knowledge of any programming language - anyone can learn this from scratch. Most of the research can be done using the Web and the library.

Back to the list.

Explore Individual Difference in Handwriting

Handwriting experts can look at a sample piece of handwriting and determine whether it is authentic or a forgery. They accomplish this task by looking at the way the words are written---the thickness of the stroke, the slant of the letters, the spacing between the letters, etc. Each of these these characteristics is called a feature of the handwriting. Come up with a set of your own set of features for analysing handwriting, and then write a computer program to automatically extract these features from hand-written letters. Time permitting, collect handwriting samples (using a program that we will provide to you), and then plot the features extracted from the various samples using a data graphing program.

Back to the list.

Implement a statistical classifier

In class we will look at a simple statistical classifier: the perceptron. Choose another classifier, such a nearest-neighbor classifier, a parzen-density classifier, or, if you are really ambitious, a support vector machine. Research this classifier, and then implement it using Matlab. Test its performance on simple examples (which we can provide for you). The programming in this project will not be complicated. The challenging part will be to understand how the classifier you choose works well enough that you understand how it can be implemented.

Back to the list.

Compare statistical classifiers

Using the statistical classifier for Matlab (which will be presented on Monday), compare the performance of several classifiers on a standard dataset, such as handwritten digits. (We can provide you with this dataset--or, for a more advanced project, you can collect your own. But chances are, collecting your own, and getting them into the correct format will become a project in and of itself). Which classifiers work well? Which do not work as well? Research each of the classifiers you compare and try to explain their relative performance. This project can be done with little or no programming.

Back to the list.

Implement a recipe sorter (or other GUI) in C#

Implement a GUI-based program in C#, for example, a program that allows a user to enter and find recipes through a graphical user interface. The program can be as fancy as you like (although we recommend starting simple). This project could take a fair amount of programming, depending on the application you choose to implement. You do not have to know how to program already, but you have to be willing to work at it, and become comfortable reading documentation. We will help you the best we can, but we may not be able to guide you through everything you need to know in the time we have with you.

Back to the list.