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
See the calendar for exceptions.
Automata, Computability, and Complexity
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.
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
- Introduction to Languages and the Theory of
Computing, John Martin
- Automata and Complexity, Dexter Kozen
- Computers and intractability : a guide to the theory of
NP-completeness, Michael Garey and David S. Johnson.
Check the course website and/or email the TA to receive extra copies of handouts and supplemental readings.
There are two course mailing lists. The first, firstname.lastname@example.org reaches only the
course staff. The second, email@example.com
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
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.
- Homework: 30%
- Quizzes: 30%
- Final Exam 30%
- Participation in class and recitation sections 10%.
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
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.
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.
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
The final has yet to be scheduled.
Last modified: Wednesday, March 31, 2004