Course Project

Your project may be on essentially any topic related to the material in the course. The best project idea is one in which you are interested! Please feel free to propose your own idea, or adapt one of the following suggestions.

Logistics

Project Ideas

  1. Many classes of randomly generated problems exhibit a "phase transition" in problem hardness. For example, see: Develop a random problem generator for Sudoku problems, and determine the parameter settings that lead to the hardest problems, independent of size. (One approach: start with a pre-exisiting Sudoku generator, and vary the output by erasing a percentage of the clues.) Determine if the hard region is sharply peaked (a first-order phase transition), or more gradual (a second-order phase transition). Consider also the distribution of individual problem hardness at the hardest parameter setting: are all "hard" problems equally hard, or if not, what is the shape of the distribution? Relate your observations to those made in the papers above.
  2. Create a variation of Walksat that outperforms it on some class of problems. (You may design the class of problems yourself.) Compare performance against walksat on a set of benchmarks, such as: The following papers are recent examples of interesting improvements of Walksat: One approach that has seen little attention is a genetic algorithm variation (exchanging information between multiple search points).
  3. If you are into music and have a large collection of mp3's: build a program that generates high-quality playlists (better than random0, taking into account what kind of songs "go together" and are appropriate for different times of the day or activities.
  4. Create a heuristic search web crawler.  Some web crawling software is available at http://www-2.cs.cmu.edu/~rcm/websphinx/ . Variations could include:
  5. One of the first machine learning programs ever written (long before there was a field of machine learning) was a "mind-reading" program for the following game:  on each trial you and the machine simultaneously type either 0 or 1.  If they match, the machine wins, otherwise you win.  The program wins by discovering subtle patterns in your attempt to type randomly.  Research, recreate, and possible improve a version of such a mind-reading program.  The original paper on this work is:  D. Hagelbarger, "SEER, A SEquence Extrapolating Robot," I.R.E. Trans. Electronic Computers, vol. 5, pp. 1-7, 1956. Doing this well will involve a literature review on current techniques for sequential prediction tasks.
  6. Apply a local search algorithm to the problem of automatic generation of computer programs.  For example, Donald Knuth's work on SortNet used genetic algorithms to find small circuits for sorting numbers.  
  7. Build a Prolog natural language parsing system that could work as the front end to a computer game you enjoy. If the game is open-source or has an open API, try getting the parser to work with it in real time.
  8. Devise a theorem-proving system for some (small) subset of mathematics.  The challenge would be to prove an open problem in algebra or mathematics in general. It's unlikely you would succeed in cracking a real open problem, but a course project would give you a better understanding of the issues and may put you on  the path of solving an open problem in the future. See McCune's page for some background, and a view of search intensive theorem proving.
  9. Create a program that solves crossword puzzles given ordinary English language clues.  See work by Michael Littman for an approach that was quite successful.
  10. Create a reinforcement learning system that learns to play a game by playing games against itself. (I recommend a game easier than Backgammon, however.)