6.889: Algorithms for Planar Graphs and Beyond (Fall 2011)
[Problem Session Notes]
Project Ideas: see here (password-protected)
The main requirement for this class,
other than problem sets,
is the project. The project consists of:
Projects can take many different forms.
Here are the five main general categories:
- A paper describing what you did.
This should be a well-written document describing the problem
you tackled (be it an implementation or a mathematical
challenge), what approaches you took, what difficulties you encountered,
and what results you found, in addition to citing the relevant literature.
Aim for on the order of 10 pages, say in the range 5–20 pages.
- If your project involves writing software, then you should submit
the source code.
- Implement an algorithm, an illustration of a result, or
a tool for experimenting with a problem.
- Survey a collection of 2 or 3 or more related papers.
- Review a paper in detail, cristalizing the most important aspects
of an algorithm and elaborating on why it can/cannot be extended to
more general classes of graphs.
- Pose an open problem (or collection of related open problems).
You might pose open problems related to another field of research
with which you are familiar, or pose something that comes to you out of
Ideally you should think about solving the problem, or how it relates
to other problems.
- Try to solve an open problem.
This is the most ambitious kind of project, so the expectations in terms
of results are correspondingly lower. What is important is to describe
a clear problem, take (at least) one good approach to that problem, and
describe to what extent it worked or did not work. You should not feel
pressure in terms of grades to produce results, but you should spend
time thinking and trying to solve the problem. (In particular, if you
succeed, you/we can write a research paper and try to publish it.)
Collaboration is particularly encouraged for projects of this type,
as is participation in the open-problem solving session.
No matter what you choose, project proposals must be approved by the instructors.
You should do this as soon as possible, and no later than
Wednesday, November 2, 2011.
Project proposals are due Wednesday, November 2, 2011,
via email to the instructors.
By MIT policy, the paper is due on the last regularly scheduled lecture
of this class, Wednesday, December 14, 2011.
Collaboration is strongly encouraged, especially for research
is often the key to successful research in theoretical computer science.
You can work in a small group of students in the class if you find common
interests. (Keep in mind that students listening to the class will have
less time to devote, but they are welcome to participate in a project too.)
You are also welcome to collaborate with anyone outside the class,
including your research supervisor (if you have one) and including me.
The only constraint for the class is that your own contribution should be
substantial enough, both in terms of solving problems and writing it up.
To evaluate "substantial enough", you should talk to me.
In any case, you should tell us who you are working with as the collaborations
arise (i.e., before you turn in your project paper). Collaborations should
also be clearly marked on the paper and presentation slides.