6.892 Algorithmic Lower Bounds: Fun with Hardness Proofs (Spring 2019)

Prof. Erik Demaine       TAs: Jeffrey Bosboom, Jayson Lynch

Policies

• 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 \includegraphics.
  • 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.

Problem Sets