6.892 Algorithmic Lower Bounds: Fun with Hardness Proofs (Spring 2019)
Prof. Erik Demaine
TAs: Jeffrey Bosboom, Jayson Lynch
[Problem Sets] [Project]
- Late policy. You can request an extension of up to two days on any problem set by emailing your issue (heavy workload, travel, sickness, hangover, etc.) to 6892-staff#at#csail.mit.edu before the problem set is due; reasonable such extension requests will be approved. You can request further extensions by emailing 6892-staff#at#csail.mit.edu and committing to not looking at the released solutions, and problem sets extended beyond two days have a maximum score of 50% and aren't guaranteed feedback from the graders. Exceptions to this (extensions granted after the deadline or extensions of more than two days without penalty) require a note from a dean.
- Collaboration policy. You may discuss assigned problems with other students, but must write your solution individually. You must wait at least an hour and do something unrelated to the problem set between working with others and writing up your answer. You must also begin thinking about each problem on your own before discussing with others.
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.
- Format. The main text of your answers must be typeset in LaTeX,
e.g., starting from this template.
Feel free to include figures however is most convenient, e.g.,
hand drawing and scanning and including via
- If you are not familiar with LaTeX, start with this
good introduction. You need to know very little to start
writing problem sets in LaTeX: just skim through the mathematics
section in the introduction, and download the template. On Athena, you can compile
with latex and view the resulting DVI files with
xdvi (which will refresh automatically when you
recompile). When you're ready to submit, compile with
pdflatex and submit the PDF.
- Gradescope. Submissions must made through
the class Gradescope page
and consist of a compiled PDF document.
Grades and comments will be posted to Gradescope.
- Problems will be graded on a 0–3 scale:
- 0 =
Your solution is far from a good one, e.g., the reduction is incorrect
or vaguely specified, and not easily fixable.
- 1 =
Your solution is on the right track to a good one, but the write-up
contained major errors or omissions, e.g., you didn't prove what you need
for correctness of your reduction.
- 2 =
Your solution is close to a good one, but the write-up contained some
minor omissions or errors, or it was poorly worded.
- 3 = Nailed it.
- Problem sets are generally due at NOON on the specified day (i.e., the night before), typically the Tuesday after it is assigned.
|February 6, 2019
||February 12, 2019
|February 13, 2019
||February 19, 2019
|February 20, 2019
||February 26, 2019
|February 27, 2019
||March 5, 2019
|March 6, 2019
||March 12, 2019
|March 13, 2019
||March 19, 2019
|March 20, 2019
||April 2, 2019
||PS7: Project Proposal
|April 10, 2019
||April 16, 2019
||PS8: Project Report 1
|April 17, 2019
||April 23, 2019
||PS9: Project Report 2
|April 24, 2019
||April 30, 2019
||PS10: Project Report 3