Project

Requirements

1. The project can be done alone or in a group of two.
2. Your project should include:
   • a programming component (write your own program or install some public domain software and use it to solve a problem of interest),
   • a short literature search component (read a few papers related to the topic of your project and report on them),
   • an original experimental component (run the program on a new problem of your own choice and analyze the results),
   • a written report.
3. A One or two-page proposal is due October 21. This should include
   • team members,
   • a brief description of the problem you intend to address,
   • the approach you will take to solve it,
   • the software you'll need to write or use,
   • how you will evaluate your solution.
   • 2-3 relevant papers you will read.
4. The project report is due Tuesday December 9 . The report should include:
   • Title, authors, date, a short abstract.
   • A short description of your problem and why it is interesting (1-2 pages).
   • A brief review of the background of your problem (1-2 pages). This should include other known solutions from the literature
   • A description of your approach to solving the problem. Include both representation and algorithms (1-2 pages).
   • Description of the design of the experiments and results (2-3 pages).
   • Analysis of the results (1-2 pages).
   • Conclusions, summarizing the problem and results and outlining future work you would do to make further progress (0.5-1 page).
   • Bibliography.
5. Graduate students who want to use their project for their Plan C should contact me to arrange for a presentation of their project.
6. Each student is expected to spend at least 50 hours on the project, including the initial research, programming and evaluation, and writing the report. The scope of the project should reflect this level of effort.

Grading

• One or two page proposal: everyone will receive 10 points for the first part (with the usual 10% a day late penalty).
• Project report: a maximum of 90 points will be given (again with a 10% a day late penalty - up to a maximum of 50%). The points for the second part will be allocated as follows:

  Overall:	writing and organizational quality of report (max 10)
  	complexity of problem and appropriateness of solution (max 15)
  Literature search:	coverage and analysis (max 15)
  Programming:	quality and complexity (max 20)
  Experimental part:	design and extensiveness of experiments (max 20)
  	analysis of results (max 10)

Ideas for Project

• Write an automated player for a non-trivial two-player game, like Othello or 3D Tic-Tac-Toe.
• Write a a simple spam filter based on naive Bayes probability, following the steps outlined in A plan for Spam by Paul Graham. The article describes the problem and provides an outline of the method to be used. The article provides some Lisp code, and Paul Graham provides more useful Lisp code. You do not need to do this in Lisp, any language will work, but it is particularly simple to write it in Lisp. If interested in using lisp for this, look here for more details.
• Use A* to find shortest paths in a map of Minneapolis, shown here. This is an old dataset, so the old 35W bridge is still there! The map data are in the file map.lisp .
  The format of the file is as follows: each line contains information about a segment of a road. Each line includes 5 numbers in parentheses. The first number is 1 to indicate a one way road or 2 to indicate a two-way road. The next two integer numbers are the x and y coordinates of the start of the segment, the next two numbers are the x and y coordinates of the end of the segment, For instance, (1 1121 7568 1042 7545) indicates a one way road starting at point [1121, 7568] and ending at [1042, 7545]. There are 1357 lines in the file, each corresponding to a road segment.
  You do not need to use Lisp, the lisp format is used for the data because of convenience.
• Solve the Traveling Salesperson Problem using real data. Large data sets are available at http://www.tsp.gatech.edu/index.html
• read the paper How MapQuest Works and implement one of the search algorithms described in there.
• read Computational Complexity of Air Travel Planning, by Carl de Marken. and propose an algorithm to solve a part of the airline search problems described in the paper.
• RoboCup runs a simulation league where a team of simulated robots plays soccer against another team. Visit the official site at http://www.robocup.org/ for information about the different leagues. The server for the simulation league is available at http://sserver.sourceforge.net/. You'll have to write a client to control a player.
• The RoboRescue simulation league addresses problems related to automating disaster management. There are two subunits, the Agent Simulation and the Virtual Robots. The agent simulation focuses on large scale (city level) planning for disaster management, while the virtual robots provides a realistic simulation environment for robots. Look at http://www.robocuprescue.org/simleagues.html for information and for the simulator.

Help for Literature Search

• Go to the ACM Digital Library, which is accessible to students and faculty. If the link does not work, you can get to it from the UofM library page on electronic journals www.lib.umn.edu/articles/ej.phtml.
• use Google with a few key terms. In general you will find lots of references.
• Go to the ResearchIndex at citeseer.ist.psu.edu. This is a good collection of searchable on-line papers. In addition to the papers, it provides links to the references and information on similar papers.

Avoiding Plagiarism

Typesetting your papers: Where to find information on LaTeX.

• Visit TUG, the T_EX Users Group site. Here you can get documentation here and visit the pages of different packages.
  Look at the page "Getting Started with TeX and LaTeX". Specially useful for beginners are:
  • LaTeX: from quick and dirty to style and finesse by Prof Tony Roberts. It is short and basic and covers all you need to write your project report.
  • A Simplified Introduction to LaTeX by Harvey J. Greenberg.
  • The not so Short Introduction to LaTeX2e Or LaTeX2e in 95 minutes by Tobias Oetiker. (PDF file).
  • Here is a set of basic latex instructions you'll need:

    \documentclass[11pt]{article}  % 11 points is a good size
    \usepackage{fullpage}          % more lines and longer lines per page
    \begin{document}
    \title{Whatever}
    \author{your name}
    \date{}	                       % avoids printing the date
    \maketitle
    \section{Introduction}
    % ..  whatever you want.  Each section should start with its title.
    \bibliographystyle{plain}      % biliography style
    \bibliography{mybibliofile}    % uses your bibliography file
    \end{document}
    

    To generate the output type

    latex myfile
    bibtex myfile
    latex myfile
    latex myfile

    To preview the output use xdvi myfile
    Once happy, use dvips -Pcmz myfile.dvi -o myfile.ps to generate postscript.
    Convert to pdf by doing ps2pdf myfile.ps
    To generate bibliographic citations, you need to create a bibliography file (.bib) and use it in the \bibliography command. After running bibtex, you need to run latex again twice (latex goes through your file once, so forward references cannot be filled in a single pass).
• CTAN, the Comprehensive T_EX Archive Network, is the home of all packages, tools, and documentation.
• MiKTEX The best T_EX and LaT_EX distribution for Windows. Look for a shareware editor called Win Edt which is very good. Recommended for anyone trying to learn Latex (lots of macros, and an integrated shell that allows compilation of Latex files from the editor). Additional useful tools are:
  • Ghostscript Postscript processor (supports Windows), used to print .ps files or convert them to .pdf.
  • GSview Postscript viewer (supports Windows).