18.404/6.840 Fall 2020 Online
Introduction to the Theory of Computation

Resources

• Canvas
• Piazza discussion forum
• Gradescope - log in to Canvas first if you have trouble accessing Gradescope
• Pset Partners for finding study groups
• Zoom link to all live online lectures and recitations
• Zoom link to all online Instructor and TA office hours

Information and Homework Handouts

• Course Information
• Schedule
• Problem Set 1 - source - solutions**
• Problem Set 2 - source - solutions**
• Problem Set 3 - source - solutions**
• Sample midterm exam problems and solutions**
• Midterm cover page with instructions
• Midterm** - solutions**
• Problem Set 4 - source - solutions**
• Problem Set 5

Late homework submission. You may submit any individual problems after the due date, before 11:59pm the following day, for a 1 point per problem late penalty deduction. In each p-set, you may submit some problems on time and some late. At 2:30pm on the due date, the regular Gradescope assignment will close and a new "late submission" assignment will appear. Please upload only those problems you wish to be counted as late. You may resubmit problems you submitted previously if you wish to change your answer, but these will be marked late and get the 1 point penalty. DO NOT RESUBMIT UNCHANGED PROBLEMS you submitted previously. The late submissions will override earlier submissions. Note: We cannot accept unexcused (see "Student Support" below) homework after the late submission deadline.

Lecture schedule and slides

1. PPT PDF (Sep 1) Introduction, finite automata, regular expressions §1.1
2. PPT PDF (Sep 3) Nondeterminism, closure properties, FA → Reg Exprs §1.2–1.3
3. PPT PDF (Sep 8) FA ← Reg Exprs, Regular pumping lemma, CFGs §1.4–2.1
4. PPT PDF (Sep 10) Pushdown automata, CFG ↔ PDA §2.2
5. PPT PDF (Sep 15) Context-free pumping lemma, Turing machines §2.3,3.1
6. PPT PDF (Sep 17) TM variants, Church-Turing thesis §3.2–3.3
7. PPT PDF (Sep 22) Decision problems for automata and grammars §4.1
8. PPT PDF (Sep 24) Undecidability §4.2
9. PPT PDF (Sep 29) Reducibility §5.1,5.3
10. PPT PDF (Oct 1) Computation history method §5.2
11. PPT PDF (Oct 6) Recursion theorem, logic §6.1–6.2
12. PPT PDF (Oct 8) Time complexity §7.1
    (Oct 13) NO CLASS — Monday schedule due to Indigenous Peoples' Day
13. (Oct 15) Midterm Exam
14. PPT PDF (Oct 20) P and NP, SAT, poly-time reducibility §7.2–7.3
15. PPT PDF (Oct 22) NP-completeness §7.5
16. PPT PDF (Oct 27) Cook-Levin theorem §7.4
17. PPT PDF (Oct 29) Space complexity, PSPACE §8.1–8.2
18. PPT PDF (Nov 3) Savitch's theorem, PSPACE-completeness §8.3
19. (draft) PPT PDF (Nov 5) Games, Generalized geography, L and NL §8.3–8.4
20. (Nov 10) NL-completeness, NL=coNL §8.4
21. (Nov 12) Hierarchy theorems §9.1
22. (Nov 17) Provably intractable problems, oracles §9.2
23. (Nov 19) Probabilistic computation, BPP §10.2
    (Nov 24) NO CLASS — Thanksgiving week
    (Nov 26) NO CLASS — Thanksgiving week
24. (Dec 1) An interesting language in BPP, Arithmetization §10.2
25. (Dec 3) Interactive proof systems, IP §10.4
26. (Dec 8) coNP ⊆ IP §10.4

Course Staff and Zoom Office Hours

• Lecturer: Michael Sipser, Tu 4-5:30
  
• TA: Fadi Atieh, fadi77@mit.edu, Mo 9-11am
  
• TA: Damian Barabonkov, damianb@mit.edu, Tu 10-12noon
  
• TA: Di-Chia Chueh, chueh@mit.edu, We 5-7pm
  
• TA: Alexander Dimitrakakis, dimitral@mit.edu, We 9-11am
  
• TA: Thomas Xiong, txiong@mit.edu, Mo 4-6pm
  
• TA: Abbas Zeitoun, zeitoun@mit.edu, Mo 6-8pm
  
• TA: Emily Liu, Grading Coordinator, emiliu@mit.edu, We 11-1pm

Lectures and Recitation Sections

• 10:00am, Alex
• 11:00am, Damian
• 12:00pm, Fadi
• 1:00pm, Abbas
• 2:00pm, Thomas

Recitation Notes

1. September 4 - Damian's notes
2. September 11 - Damian's notes - Alex's notes
3. September 18 - Damian's notes - Abbas's notes
4. September 25 - Damian's notes - Fadi's notes
5. October 2 - Alex's notes
6. October 9 - Damian's notes - Abbas's notes
   October 16 - No recitations this week
7. October 23 - Damian's notes
8. October 30 - Damian's notes - Fadi's notes - Thomas's notes
9. November 6 - Damian's notes

Other Information

Check-in Quizzes: Following student recommendations, we will de-emphasize (but not eliminate) the midterm and final exams by adding graded live check-in quizzes for credit during the lectures, to be conducted via Zoom's polling feature. The check-in quizzes (aka check-ins) are listed under the Quizzes tab in Canvas. For students viewing a recorded lecture, an alternate timed and graded recorded check-in quiz will be available but it must be completed within 46 hours of the original live lecture. You may may chose whether to take the live check-in or the recorded check-in, but you must take one or the other to receive credit. The live check-ins won't be graded for correctness. You will receive full credit for submitting any answer, correct or not. The recorded check-ins will be graded for correctness but you may take these as many times as you like before the closing time. If you take one or more recorded check-ins, the last grade will override previous live or recorded check-in grades.

Required background: To succeed in this class, you need a good facility with mathematical concepts, theorems, and proofs. If you did reasonably well in 6.042, 18.200, or any other substantial, proof-oriented mathematics class, you should be fine. The class moves quickly, covering about 90% of the textbook. The homework assignments generally require proving some statement, and creativity in finding proofs will be necessary.

Exam Schedule

Midterm exam: Thursday, October 15, 2020, 90 minutes, start time flexible.
Final exam: Thursday, December 17, 2020, 3 hours, start time flexible.

Student Support

If you may require disability accommodations, please speak early in the semester with Associate Dean Kathleen Monagle at 617-253-1473 and then let me know so that we can work together to get your accommodation logistics in place.

Accessibility