6.890 Algorithmic Lower Bounds: Fun with Hardness Proofs (Fall 2014)
Prof. Erik Demaine
TAs: Sarah Eisenstat, Jayson Lynch
[Problem Sets] [Project]
- 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
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
- 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
(for the more coding minded)
- 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.