CS 466/666 Final Project

For the final project, you will be asked to do one of the following:

  1. work on an open problem in algorithm design and present a survey about the problem and the outcomes of your investigations at the end of the term,
  2. present a survey of a topic of your choice (see some example topics below), and analyze one of the main algorithms in that topic.

The ideal project would be a problem/topic that you are excited about - this often brings one the most joy. If you need some guidance in picking a problem to present on, I will be happy to meet with you to hone into a problem of your liking.

The topics below are simply a suggestion. If you have another topic of your interest which is not covered here, I will be happy to try and work out with you a possible project on your topic of choice.

Students can work in groups of at most 2 people.

Timeline for the final project

  • May 31st: decision on project groups due
  • June 28th: project proposals due
  • July 15th: revised proposals due
  • August 7th: project reports due

Requirements for the project proposal

In your project proposal, I would like a 1-page document (in LaTeX format - you can use this template) containing the following information:

  • Title of your project
  • Brief statement on the problem you will be working on
  • Main algorithm that you will analyze (or main problem you will try to solve, or main lower bound you will present)
  • Reference for the main algorithm
  • Auxiliary references

Requirements for the final report

A good final report will be one which can summarize in ten pages:

  • a good introduction to the problem being studied (why is it relevant/previous results/current state of affairs),
  • a summary of your approaches (if you decided to work on an open problem),
  • progress made (if you manage to make any, even in particular special cases of the problem)
  • analysis of one of the current best algorithms that solves your problem
  • conclusion with open questions.

The limit to 10 pages is simply because this is a constraint that even us researchers have when submitting a paper to a conference, so it should be doable to you as well, plus it is great practice.

Plus I intend to read all of them, and this limit will put my reading to somewhere between 300-600 pages.

Note: the references need to fit in the 10 pages.

Template for final report

For the final project, we strongly recommend you to write it in LaTeX. A template that you can edit accordingly is given here.

Grade rubric for final project

The final project will be worth 100 points, allocated as follows:

  • 10 points: project proposal sent to me on time
  • 10 points: successful revised project proposal agreed upon
  • 80 points: project report

Research-based projects

I highly encourage you all to try your hands at an open problem! It is an amazing and enriching experience, and you may end up solving it by the end of the class!

For those of you who want to use this opportunity to start working on some research problems (perhaps as a pre URA or an URF), here are people that you can check out their webpages/try to reach out to, or resources at your disposal, for you to look for suitable projects:

A good strategy to find interesting open problems is to look at a particular faculty’s advanced graduate course’s webpage and see the topics they are interested in and the open problems in the area that they would be interested in. You can use your final project to get a deeper understanding in such an area where your interests match.

Sample Open Problems

  • Is hyperbolic programming equivalent to semidefinite programming?
  • Can one give rigorous guarantees on algorithms for metropolis light transport in graphics? Reference
  • Can one efficiently count the number of perfect matchings in bipartite graphs of bounded treewidth? What about graphs with excluded minors? (see below for references on this problem)
  • Open problems in sublinear time algorithms
  • Polynomial time quantum algorithm for graph isomorphism problem? More generally, see Lomont’s survey of open problems about the hidden subgroup problem.

Possible Survey Topics for Final Project

You can also find open problems here!

Previous

Last updated on Sep 1, 2010

Edit this page