CS 466/666, Fall 2005

Project

Home People Policies Resources Schedule Assignments Project

General information

Each graduate student (and, with approval of the instructor, each self-selected undergraduate student), will have the opportunity to conduct an in-depth exploration of algorithms and/or lower bounds pertaining to a particular problem. Students are encouraged to choose, in consultation with me, topics that are germane to their research interests. Work on a problem that ends up being part of your thesis or essay in encouraged (though handing in work you have already done for your research or in another course is not acceptable). It is best to avoid topics discussed in class. The complexity of the problem can be presented as lower bounds and/or upper bounds using one or more of the types of analysis seen in class (amortized, worst-case, average case, probabilistic, approximation, online, parameterized). Heuristics and experimental results are outside the scope of the course and hence inappropriate for the project.

The goal of your project is to discover the best algorithm or algorithms for a particular problem. It may be that you find algorithms that solve different aspects or cases of a problem, or that there is more than one algorithm that can be argued to be the best. You are encouraged but not required to try to find your own solution and add your results to the discussion. Your final paper should be approximately 7 to 15 pages long and should cover approximately 3 to 10 papers, giving a coherent summary and assessment of the various solutions. Should you find that the number of papers is much smaller or greater than the range suggested, be prepared to narrow or widen the scope as needed.

Resources

A good way to find a topic is to browse through recent conference proceedings, using the references listed as further guides into the literature. The Science Citation index (available in the library) can used to find references to seminal papers. I have compiled a list of call numbers and other resources that might be of use.

Plagiarism

Plagiarism is an academic offense and will be dealt with severely. In all your writing, all uses of other sources, whether papers in conferences or discussions with experts, should be cited clearly in the text. Quoted materials should be short in length and clearly indicated. Algorithm descriptions, proofs, and accompanying text should all be written in your own words.

Topics

Here are a few ideas for topics; they may need to be widened or narrowed to ensure the right size of a problem. One source is NP-complete problems: see if it is possible to find exact algorithms by restricting the problem (e.g. graph problems on trees or planar graphs, TSP with various constraints), or consider approximation algorithms or fixed-parameter tractability results for these problems. Possible topics include the following problems and their many variants: scheduling problems, knapsack, bin packing, nearest neighbour search, pattern matching (strings, trees, or graphs with or without mismatches), Steiner trees, and finding long paths. I will not accept papers on the topic of primality testing, so please do not choose it. You may wish to consult the on-line compendium of NP optimization problems for further ideas.

Checkpoints

The mark on the project will depend not only on what is handed in at the end of the course, but also on the timely completion of various checkpoints along the way. You are encouraged to finish each checkpoint as early as possible; the sooner you give me partial work, the sooner I can give you feedback that will enable you to rapidly progress on the rest of the project. Moreover, topics will be given to those who first request them. The checkpoints are as follows, with deadlines listed below.

Proposal: a paragraph or two describing what you intend to do for your project. The purpose of the proposal is to ensure that your choice is appropriate in scope and content, and that students choose different topics.
Outline and bibliography: two or three pages of detailed description of your project, plus the bibliography of references that you will be using.
Complete project: see expectations below.

	Checkpoint	Due date
	Proposal	21 October in class, 10:30
	Outline and bibliography	11 November in class, 10:30
	Complete project	5 December in class, 10:30

Expectations for full marks

Your project needs to demonstrate both the breadth and the depth of your knowledge of the work on the topic. For breadth, you should should give a survey of the major results on the problem, not necessarily just those which are recent enough to be available on the Web. Be sure to organize the results in a logical manner, pinpoint what is important and new in each result, and find a common set of terminology to discuss all results in a uniform manner. For depth, include a more detailed description (in your own words!) of a few of the most important algorithms or lower bounds. Including your own ideas is a good way to show how well you have undertood the papers. If possible, conclude your paper with a discussion of what is left to be done on the problem (or closely related ones). Your paper will be marked not only on the completeness of your search and demonstrated understanding of the material included, but also on the quality of the paper's organization and writing. Don't be seduced by the elegance of a typeset document; proofread it ruthlessly. Use a spell checker, but remember that there are many errors that it will not catch. Consider consulting a style guide; I've compiled a short list of guidelines.