6.045 - Automata, Computability, and Complexity Theory - Spring 2017

ryan's classy diagram

[General Info]   [Lectures]   [Homeworks]   [Exams]

General Information

  • 6.045 on Stellar
  • Course Staff and Physical Office Hours
  • Announcements on Piazza (Virtual Office Hours) Sign up with Piazza to stay updated on the course!
  • Rather than emailing questions directly to the teaching staff, we strongly encourage you to post your questions on Piazza. If you have any problems or feedback for the Piazza site, please email team@piazza.com (and feel free to cc rrw).


    Note: the 2nd edition of Sipser is also fine for this course, if you can find it cheaper!

    Grading: Midterm exam: 25%, Final exam: 35%, Homework: 40%.

    Homeworks/Problem Sets:


    [Jump to What's Ahead]

    SO FAR:

    1. 02/07 Introduction and course summary; Finite automata, DFAs and NFAs
      Readings: Sipser, Chapter 0, 1.1
      Slides: [color pdf] [grayscale pdf]

    2. 02/09 SNOW DAY -- NO CLASS

    3. 02/14 DFAs and NFAs, equivalence of DFAs and NFAs
      Readings: Sipser 1.1, 1.2
      Slides: [color pdf] [grayscale pdf]

    4. 02/16 Regular expressions; Equivalence of automata and regular expressions
      Readings: Sipser 1.3
      Slides: [color pdf] [grayscale pdf]

    5. 02/21 YOUR MONDAY CLASS GOES HERE -- NO 6.045

    6. 02/23 Proving languages are not regular; start Minimizing DFAs
      Readings: Sipser 1.4, Sipser Problem 7.40 in 2nd ed (7.25 in 3rd ed) and its solution
      Slides: [color pdf] [grayscale pdf]

    7. 02/28 DFA Minimization, part 2
      Readings: Our lecture notes, Sipser Problem 1.52 in 2nd ed (1.48 in 3rd ed) and its solution
      Slides: [color pdf] [grayscale pdf] [VIDEO mp4]

    8. 03/02 The Myhill Nerode Theorem; Streaming Algorithms: Small Algorithms for Big Data
      Readings: Some lecture notes on streaming algorithms
      Slides: [color pdf] [grayscale pdf]

    9. 03/07 More on Streaming Algorithms; start Communication Complexity
      Readings: Some lecture notes on streaming algorithms
      [Optional reading] A Communications of the ACM and an Encyclopedia of Algorithms article on finding frequent elements
      Slides: [color pdf] [grayscale pdf]

    10. 03/09 More on Communication Complexity; start Turing Machines
      Readings: Sipser Chapter 3, and Turing's amazing paper (also here)
      [Optional reading] A survey on communication complexity
      Slides: [color pdf] [grayscale pdf]

    11. 03/14 Church-Turing Thesis, Decidability, Recognizability
      Readings: Sipser 4, 5.1, 5.2
      Slides: [color pdf] [grayscale pdf]

    12. 03/16 Diagonalization, Undecidability, and Reductions
      Readings: Sipser 5.3, 6.3
      Slides: [color pdf] [grayscale pdf]

    13. 03/21 Diagonalization revisited, Proving Undecidability via Reductions
      Readings: Sipser 6.1, another take on Rice's theorem
      Slides: [color pdf] [grayscale pdf]

    14. 03/23 Midterm (During class time! --- located at 50-340)

      03/28 and 03/30 SPRING BREAK -- NO CLASS

    15. 04/04 Rice's Theorem, Oracles, Self-Reference, the Recursion Theorem
      Readings: Sipser 6.2
      Slides: [color pdf] [grayscale pdf]

    16. 04/06 Computability and the Foundations of Mathematics
      Readings: Luca Trevisan's notes on computability and logic
      Slides: [color pdf] [grayscale pdf]

    17. 04/11 Kolomogorov Complexity
      Readings: Sipser 6.4
      Slides: [color pdf] [grayscale pdf]

    18. 04/13 Time Complexity and the Time Hierarchy Theorem
      Readings: Sipser 7.1, 7.2, 9.1
      Slides: [color pdf] [grayscale pdf]


    20. 04/20 $P$ and $NP$; Polynomial-Time Reductions
      Readings: Sipser 9.1, 7.3, 7.4
      Slides: [color pdf] [grayscale pdf]

    21. 04/25 (Guest Lecture) The Cook-Levin Theorem; $NP$-completeness
      Readings: Sipser 7.4, 7.5, an alternate proof of the Cook-Levin Theorem
      Slides: [color pdf] [grayscale pdf]

    22. 04/27 (Guest Lecture) $NP$-completeness of clique, vertex cover, independent set and subset sum, knapsack, bin packing
      Readings: Sipser 7.5, Luca Trevisan's notes
      Slides: [color pdf] [grayscale pdf]

    23. 05/02 NP-completeness of Hamiltonian path, $coNP$ and Friends
      Readings: Sipser 7.5, 9.2
      Slides: [color pdf] [grayscale pdf]

    24. 05/04 Oracles in Complexity Theory, $P^{NP}$, $NP^{NP}$, $coNP^{NP}$
      Readings: Sipser 9.2
      Slides: [color pdf] [grayscale pdf]

    25. 05/09 Space Complexity, $PSPACE$ and $EXPTIME$
      Readings: Sipser 8.1, 8.2, 8.3
      Slides: [color pdf] [grayscale pdf]

    26. 05/11 $PSPACE = NPSPACE$, $PSPACE$-complete problems
      Readings: Sipser 8.1, 8.2, 8.3
      Slides: [color pdf] [grayscale pdf]

    27. 05/16 Finish PSPACE, Randomized Algorithms and Complexity ($RP$ and $BPP$)
      Readings: Sipser 10.2
      Slides: [color pdf] [grayscale pdf]

    28. 05/18 More on Randomized Complexity, Course Summary
      Slides: [color pdf] [grayscale pdf]

    29. WHAT'S AHEAD

    30. Study for the final exam!


    Homework comes out on Wednesdays and is due the following Wednesday at 11:59pm. You are required to compose your homeworks in some word processor (LaTeX is preferred); we will provide source code to get you started.

    Homeworks are posted HERE.


    Midterm: The midterm will be in-class, on Thursday, March 23 in room 50-340. For this exam, we allow one single-sided sheet of notes (on the usual 8.5x11 letter paper); otherwise, the exam is closed-book.

    IMPORTANT: If you have a conflict with the midterm time, please email the entire course staff with the subject line "Midterm Conflict". We'll schedule a conflict midterm during the week after spring break.

    Final Exam: Room 4-270, Friday, May 26 1:30PM - 4:30PM according to this webpage. For this exam, we will allow one double-sided sheet of notes; otherwise, the exam is closed-book.