6.889: Algorithms for Planar Graphs and Beyond (Fall 2011)

Erik Demaine, Shay Mozes, Christian Sommer, Siamak Tazari

[Home] [Problem Sets] [Project] [Lectures] [Problem Session Notes] [Klein's Book] [Accessibility]

Problem Sets

Problem sets will be posted here periodically, with announcements to the class mailing list. You are welcome to collaborate on problem sets, but your write-ups must be your own, and your problem sets must list your collaborators.

Problem Set	Due
PS1	9/22 at noon	solution
PS2	9/28 at noon	solution
PS3	10/5 at noon	solution
PS4	10/12 at noon	solution
PS5	10/19 at noon	solution (this is a paper by Demaine and Hajiaghayi)
PS6	10/26 at noon	solution
PS7	11/2 at noon	solution
PS8	11/9 at noon	solution	you may use this hint.
PS9	11/16 at noon	solution	corresponding book chapter
PS10	11/23 at noon	solution
PS11	12/7 at noon	solution

Policies

There will be roughly weekly, one-page problem sets.
Solutions will be posted here after the due date; for this reason, late days are not allowed.
The answers must be typeset in LaTeX, and should fit in one page. Figures can be on additional pages. Problem sets whose text is more than one page risk being read and scored less. Use at least 10 pt font and 1 inch margins. This rule is meant to prepare you for writing research publications: one often has to explain great ideas in a very limited number of pages.
Submissions must be via email to 6889-ps#at#csail.mit.edu and include a compiled PDF attachment. The file name should follow the pattern: [initial][last-name]-ps[number].pdf; for example, a solution to the 3rd assignment from John Doe should be named jdoe-ps3.pdf.
Solutions do not need to include all calculations, trivial details, etc. Just prove to us that you found the solution, and you understand it well.
Problems will be graded on a 0-2 scale:
- 0 = You didn't get it. Filling one page to the brim does not mean you can't get zero. Please don't write stuff you know is wrong.
- 1 = Your solution was ultimately a good one, but the write-up contained significant errors or omissions.
- 2 = (We think) you got it.
Due dates are generally at the beginning of lecture on the specified day.