## 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).

Textbook:

• Michael Sipser, Introduction to the Theory of Computation (3rd Edition), Thomson
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:

• Homework/psets will come out on Wednesdays (except when an exam falls on the next week) and will be due the following Wednesday at 11.59 pm. Late assignments will not be accepted. To account for this, we will drop the lowest homework grade in computing your final grade. If you are unable to submit your homework because of extenuating circumstances such as a family/medical emergency, please contact Ryan or the TAs about it (ASAP).

We require that you write your homeworks using a word processor that can generate PDFs. If you can generate a readable typeset PDF of your pset (i.e., in a clean font that is not your handwriting), we are OK with whatever system you use. We strongly recommend that you write your homeworks in LaTeX; we will provide the LaTeX source code for every homework assignment! (Exception: Hand-drawn figures are allowed; you can scan them and merge them in your PDF.) Practically every paper published in computer science and mathematics nowadays is written in LaTeX, so the ability to write in LaTeX is a very useful skill. If you use Windows, MiKTeX is a good choice. Grading will be done by TAs and/or Graders, possibly using Gradescope.

Most of the work in this course will be mathematical proofs of various cool facts. Your proofs should be as clear as possible. Note, this does not mean your proofs should be long -- in fact, typically, good clear explanations are also short!

• Policy on Collaboration: This is very important; please read carefully. We believe that the best learning often happens when you work with others, and we want to encourage that. But it is equally important that you try to learn on your own! So here are our rules for collaboration on homework:
• You must think about all homework problems on your own and do your very best to find the solutions yourself, before discussing/collaborating with other students. After failing to find the answers yourself, you may discuss homework problems with other students, and work in groups on the remaining questions.
• You must not look for solutions on the web. Instead, ask us questions if/when you get stuck.
• Cite properly! If you work in a group, include the names of the other people in the group in your written solution. In general, if you do receive a significant idea from someone or somewhere, you must acknowledge that person/book/website in your solution.
• You must write up your own solution to every problem; you may not copy answers from another student, or any other source. Also, you may not show your answers to another student. Failing to follow this rule may constitute plagiarism.
Deviating from the above rules may result in violation of MIT policies. If you have any questions about our policy, please don't hesitate to send a private note to the course staff on Piazza. We have these rules so that you can learn on your own, and also learn from your classmates. They're actually pretty lax compared to other courses, so please respect them!

• How to write/submit homework: To be announced.

• Regrade Policy: If you wish to request a regrade on a problem, you will need to prepare a written justification and come to office hours to talk about your solution in person. We require that you submit your request within one week after the homework/exam is returned.

• For all homework questions (that do not give away solutions!), please post to piazza.com/mit/spring2017/6045/home or come visit us at office hours. You can also send private questions (to TAs and instructors only) using Piazza.

## Lectures

SO FAR:

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

2. 02/09 SNOW DAY -- NO CLASS

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

4. 02/16 Regular expressions; Equivalence of automata and regular expressions
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
Slides: [color pdf] [grayscale pdf]

12. 03/16 Diagonalization, Undecidability, and Reductions
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
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
Slides: [color pdf] [grayscale pdf]

18. 04/13 Time Complexity and the Time Hierarchy Theorem
Slides: [color pdf] [grayscale pdf]

19. 04/18 PATRIOT'S DAY VACATION -- NO CLASS

20. 04/20 $P$ and $NP$; Polynomial-Time Reductions
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
Slides: [color pdf] [grayscale pdf]

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

25. 05/09 Space Complexity, $PSPACE$ and $EXPTIME$
Slides: [color pdf] [grayscale pdf]

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

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

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

30. Study for the final exam!

## Homework

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.

## Exams

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.