 |
6.045/18.400
Automata, Computability, and Complexity |
|
|
|
Lectures are Monday and Wednesday, 11-12:30, in 37-212.
Recitation times are Thursdays, 10am in 34-302 and 1pm and 4pm in 34-304.
Office hours for the TA are (tentatively) Mondays 4-5pm in 32-G630 (actually somewhere close to that) and 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.
The book for this class is Introduction to
the Theory of Computation by Michael Sipser.
This term, we will use the SECOND edition of the textbook, which will
be available at Quantum Books on February 15, 2005. Prior to that
time, copies of the page proofs for the first few chapters will be
handed out in class.
The textbook will also be 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:
- 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, 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.
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: 30%
- Quizzes: 30%
- Final Exam 30%
- Participation in class and recitation sections 10%.
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.
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 his/her 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
given.
The final has yet to be scheduled.
Last modified: Wednesday, January 05, 2005