- Program the computer to play chess.
- Invent a algorithm for parallel sorting.
- Study how driving habits affect freeway traffic.
- Learn about what a computer's machine language really looks like.
- Build a simulator for some physical phenomenon.
- Investigate L-Systems and fractal growth
- Investigate cellular automata
- Investigate autonomous agents
- Explore individual difference in handwriting
- Implement a statistical classifier
- Compare statistical classifiers
- Implement a recipe sorter (or other GUI) in C#

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.

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.

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

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.

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.

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.

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.

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.

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.

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.