 |
6.045/18.400
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.
The textbook has been placed on reserve at Barker
Library, as well as five other books. 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.
- Introduction of Automata, Languages, and
Computation, John Hopcroft, Rajeev Motwani, Jeffrey Ullman
- Computation of Infinite Machines, Marvin Minsky
Extra copies of handouts and supplemental readings will be kept
in the course drawer, which is located in the 3rd floor lounge,
NE43. (The
central location for the theory floor of the LCS.)
Lectures are Monday and Wednesday, 11-12:30 in 24-121. Recitations
are at 1 and 4, Thursdays, in 34-304. Office
hours of the TA are 4:30-6, Tuesdays, in NE43-336, and by appointment. See
the calendar for exceptions.
There are two course mailing lists. The first, 6.045@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. Extensions are possible with advance
warning. The greater the warning, the more likely the odds of an
extension. No extensions will be granted the day a homework is
due, and no homework will be accepted after solutions
are posted.
With regards to homeworks: full credit will be given for correct
answers and proofs, of course. 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.
We encourage collaboration. In fact, we regard it as essential to
passing the class. We do not expect you to be able to solve every
homework problem on your own. We do expect you to write
down your solutions on your
own, however. To repeat: each person must write up their
solutions separately. Also, please note 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.
The quizzes will be held on
- Wednesday, 27 February,
- Wednesday, 3 April,
- Wednesday, 1 May
There will be no homework due on Wednesdays in which a quiz is
given.
The final has yet to be scheduled.
Jonathan Herzog
NE43-336
x3-5971
<jherzog@mit.edu>
Last modified: Tue Mar 19 16:22:38 EST 2002