6.890 Algorithmic Lower Bounds: Fun with Hardness Proofs (Fall 2014)

Prof. Erik Demaine       TAs: Sarah Eisenstat, Jayson Lynch

Policies

• There will be approximately five problem sets total, each with 2–3 weeks to complete them. We anticipate some problems being challenging and advise students to start thinking about the problems early.
• Solutions will be posted here after the due date; for this reason, late days are not allowed.
• Submissions must made electronically through the relevant problem set on the Stellar page at https://learning-modules.mit.edu/gradebook/index.html?uuid=/course/6/fa14/6.890#assignments and consist of a single PDF document. If you are not a member of the Stellar page (which you can check at https://stellar.mit.edu/S/course/6/fa14/6.890/people/membership.html) email the course staff immediately.
• Answers must be clearly written and formatted. We will deduct points if your solutions are hard to read or poorly formatted.
• We strongly encourage the use of LaTeX for written/math parts of your answers; Microsoft Word 2013 and Google Docs also have reasonable math support. If you are unfamiliar with LaTeX, start with this good introduction. You can use this LaTeX template.
• You may scan your figures, or entire solutions if your handwriting is clear. To draw figures electronically, we recommend Inkscape or (for the more coding minded) Asymptote.
• Grades and comments will be posted to the Stellar page.
• 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.
• You may discuss assigned problems with other students, but must write your solution individually.
• Be sure to cite all collaborators and any sources you use. Avoid reading sources that solve the problem, but if you accidentally do, cite that source.
• Problems will be graded with the following marks:
  • X = 0/10: You didn't get it. The answer is completely wrong or doesn't address the question. Please don't write stuff you know is wrong.
  • check minus = 6/10: Your solution had a good concept, but the write-up contained significant errors or omissions.
  • check = 8/10: Your solution was essentially correct but contained minor errors or omissions.
  • check plus = 10/10: (We think) you got it.
• Due dates are generally at 11:59pm on the specified day.
• Late problem sets will generally not be accepted unless you (1) have a dean's note or (2) request and get approved an extension from us prior to the deadline.

Problem Sets