CMPU-365, Spring 2013
Guidelines for Final Project Proposal


From the course web site:

  The final project will be an implementation based on algorithms or
  ideas covered in class, or an investigation into algorithms or ideas
  that we may have mentioned in class but did not address in depth.
  In either case, there must be a programming part and a written part
  describing what you have done.  To ensure that you get off to a good
  start, 15% of the grade for your final project will be baesd on your
  initial project proposal.  An additional 15% of the project grade
  will be baesd on a short, in-class presentation of your project.
  The in-class presentations will be given prior to the due date for
  the project so that you can receive feedback on your approach,
  progress, etc. The final project will be due at 5 p.m. on the last
  day of study period (i.e., May 14th).

So far, we have studied the following topics:

   * SEARCH (including breadth-first, depth-first, iterative
       deepening, greedy and a-star search)

   * CONSTRAINT SATISFACTION PROBLEMS (including recursive backtracking,
       with forward checking, and heuristics to guide the search)

   * ADVERSARIAL SEARCH (including minimax with alpha-beta pruning using
       static evaluation functions)

   * KNOWLEDGE REPRESENTATION AND REASONING (including first-order logic,
       proving entailment by resolution-refutation, the OTTER theorem
       prover)

   * SIMPLE TEMPORAL NETWORKS (a general overview of the basic data
       structures, representations, problems and algorithms)

We shall also be looking at neural networks in the near future.

Potential topics for your final project, grouped by the above categories,
could include:

   * SEARCH

        -- using iterative deepening a-star search and various other
           techniques for solving the 3-by-3 rubik's cube.  (See the
           paper "Finding Optimal Solutions to Rubik's Cube Using
           Pattern Databases" by Richard E. Korf for more details.)

        -- exploring the use of "local search algorithms" (e.g.,
           hill climbing, simulated annealing, or genetic search).
           (See Chapter 4 for ideas.)

   * CONSTRAINT SATISFACTION PROBLEMS

        -- develop a CSP solver that uses some of the heuristics
           discussed in class to guide the search in some domain
           of your choice.

   * ADVERSARIAL SEARCH

        -- improve the chess-playing program by augmenting the static
           evaluation function, fine-tuning the minimax search process
           (e.g., order of moves), and dealing with the opening part
           of the game or the end game.

        -- apply adversarial search to a probabilistic domain (e.g.,
           a card game or a dice-tossing game such as backgammon).

   * KNOWLEDGE REPRESENTATION AND REASONING

        -- develop a knowledge base and querying system that uses the
           OTTER theorem prover (e.g., for a course registration system,
           or a tourist database).

   * TEMPORAL NETWORKS

        -- implement an airline reservation system that uses Simple
           Temporal Networks to manage temporal constraints.  

   * NEURAL NETWORKS

        -- implement and train a neural network to predict stock market
           prices

------------------------------------------------------------------------

  IMPORTANT:  When choosing your project, be careful to pick a problem
              that is of a manageable size and complexity.  You don't
              want to end up with half a system that doesn't do
              anything.  It is much better to start with a system that
              does a little bit very well; and then extend it
              incrementally to improve its capabilities or
              performance.

  Also:  Keep in mind that you will have to test your implementation
         to demonstrate that it does what it is supposed to do.

------------------------------------------------------------------------

 THE PROPOSAL

   The proposal should be a two or three page description of the project
   you would like to work on, the goal of the project, and the manner
   in which it will be tested.  The proposal should cite any
   preliminary reading you have done (e.g., chapters in the text or
   outside papers) as well as readings you plan to do as part of your
   subsequent preparation.  It should also give a high-level description
   of the proposed implementation.

   ==> You are allowed/encouraged to work in teams of two students on
       your project.  However, you must clearly describe in your
       proposal how you plan to divide the work.  The ideal
       circumstance would be two pieces that can be independently
       developed and tested and then fit together.  However, other
       schemes are possible.

   ==> You are free to work with whomever you want (within the class!)
       on your final project. 

   ==> The students participating in team projects will not
       necessarily get the same grade.  The grades will depend on who
       did what and how well.  In group projects, each participant
       will be required to turn in a one-page summary describing what
       he or she worked on.  (That will be an addendum to the final
       report submitted by the group.)

   ==> The focus of the project should be on the relevant algorithms,
       not on extraneous things such as graphical user interfaces!

   ==> All code should be written in Lisp and executable on the
       computers in the CS department.
       
   ==> There should be a clear, concise README file submitted with 
       the program code that describes how to use your program. 

   ==> The project write-up, due when submitting the final project,
       will include an overview of the problem, your approach, your
       testing, and a discussion of the results.  The write-up is
       an important part of the final project.

============================================

   REMEMBER!  Have fun!