Automata, Computability, and Complexity

Course Home Page
General Information/Policies
Contact Info
Objectives and Outcomes
Course Materials by Lecture Date

Lectures, Recitations and Office Hours

Lectures are Monday and Wednesday, 11-12:30, in 37-212. Recitations will be held on Thursdays at 1pm in 34-304 and 4pm in 34-304. TA Office Hours will be on Mondays from 4-5pm in 32-G694 (Actually, somewhere near the TA's office in Stata Center, Gates Tower, Room 694). Additional times available by appointment. See the calendar for exceptions.


We assume that you have taken 6.042, Mathematics for Computer Science. 6.045 is, at heart, a mathematics course, and we assume that you are reasonably facile with mathematical concepts. In particular, we assume that you are comfortable with formal mathematical proofs, and can write them up properly.

Course materials

The book for this class is Introduction to the Theory of Computation by Michael Sipser. If you do not have a copy of the textbook, copies are available for purchase at Quantum Books

The textbook has been placed on reserve at Barker Library, as well as three other books that students in the course have found useful in the past. We hope that students who find the textbook unenlightening can consult these books for a different explanation:

Check the course website and/or email the TA to receive extra copies of handouts and supplemental readings.

Course Mailing List

There are two course mailing lists. The first, 6.045-staff@mit.edu reaches only the course staff. The second, 6.045-students@mit.edu reaches all staff and students. Please feel free to contact the staff via the first list, and your fellow students via the second. We especially encourage you to use the list to find collaborators.

Grading Policy

There will be (approximately) weekly homework assignments, three in-class quizzes, and a final exam. The final grade will be computed using the following weights:


Homework will be due approximately every week, at the beginning of Wednesday's lecture. We feel it is very important that you turn in the homework assignments on time and we are unable to accept late homeworks. However, when computing your grade at the end of the course, we will drop your lowest homework score. Therefore you need not worry about getting a bad grade on a single assignment.

With regards to homeworks: full credit will be given for correct answers and proofs. We will also grant partial credit for partial solutions and solutions with minor flaws. We will also give a small amount of partial credit for answers which read in full, "I don't know." Likewise, proofs with gaps will receive partial credit, and the partial credit granted will increase if the gaps are explicitly noted.We will give no credit for wildly incorrect answers which are obviously only there in the hopes of getting partial credit. Please only write down answers in which you are confident. Wild guesses only waste our time. Making yourself believe a false proof is bad for your brain.

We require that all homework solutions be typed up. We will provide LaTeX shells for you to flesh out with your solutions, but you do not need to use them. Hand-drawn diagrams are permitted. If you are unfamiliar with LaTeX, see the helpful materials from Lecture 1.

Collaboration Policy

We strongly encourage collaboration. We do not expect you to be able to solve every homework problem on your own. We do, however, expect you to write up your own solution to every problem even if the solution is the result of a collaborative effort. To repeat: each person must write up their solutions separately. Also, in your write-up please credit the people with whom you worked. If you consult any reference material other than the textbook, please note on your homework which sources you used for each problem.

Quizzes and Exams

There will be three quizzes and one final exam. The quizzes will be held during class time on Each quiz will cover a unit of the course; the final exam will be cumulative. There will be no homework due on Wednesdays in which a quiz is given.

The final has yet to be scheduled.

Last modified: Wednesday, March 31, 2004