6.5440 Algorithmic Lower Bounds: Fun with Hardness Proofs (Fall 2023)

Prof. Erik Demaine       TAs: Josh Brunner, Lily Chung, Jenny Diomidova

Policies

• There will be a weekly problem set, up to 12 problem sets in total.
• 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 6.5440-staff@csail.mit.edu before the problem set is due; reasonable such extension requests will be approved. You can request further extensions by emailing 6.5440-staff@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.
• Gradescope. Submissions must made through the class Gradescope page and consist of a compiled PDF document. Grades and comments will be posted to Gradescope. See entry code on Coauthor.
• Problems will be graded on a 0-2 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.
  • 1.5 = Your solution is close to a good one, but the write-up contained some minor omissions or errors, or it was poorly worded.
  • 2 = Nailed it.
• Due dates are generally at 11:59am (noon) on the specified day (typically Mondays and 7 days after release).

Problem Sets