6.045/18.400
Automata, Computability, and Complexity
Course Home Page
General Information/Policies
Contact Info
Objectives and Outcomes
Calendar
Course Materials by Lecture Date

Course Content and Prerequisites

This course covers basic models of computational processes: finite-state automata, Turing machines, time- and space-bounded machines, and probabilistic machines. It examines, precisely, the classes of problems that can and cannot be solved by the various kinds of machines. It tries to expose the key differences between machine models that affect their computational power.

The course is divided into three units, on finite-state machines, on computability theory, and on complexity theory.

We assume that you have taken 6.042, Mathematics for Computer Science. 6.045 is, essentially, 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.

People, Places, and Times

The course staff members are: Lectures are held Mondays and Wednesdays, 11--12:30, in 32-144. Recitations are held on Thursdays at 12-1pm and 1-2pm in 26-328. Teaching assistant office hours are on Fridays at 12-1pm, and Mondays 12:30-1:30pm in the neighborhood of 32-G614. Prof. Lynch is available by appointment, and usually right after class. See the calendar on the course web site for exceptions to this schedule.

The course web site can be found at: http://theory.lcs.mit.edu/classes/6.045/spring07

Electronic copies of handouts will be available on the site.

There are two course mailing lists. The first, sp07-6.045-staff@mit.edu, reaches only the course staff. The second, sp07-6.045@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 other students to collaborate with.

Course materials

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 is available at Quantum Books. The textbook, as well as three other books that students in the course have found useful in the past, will be placed on reserve at Barker Library and the CSAIL Reading Room. The other books are:

Extra copies of handouts and supplemental readings will be kept in the course drawer, which is located outside of the course secretary's office, 32-G672A.

Course Requirements

Grading

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

Homeworks

Homework will be due approximately every week, on Monday at 5 PM. Homeworks can be turned in, in .pdf format, by email to elena_g@mit.edu.

Of course, you can instead turn them in during class on Monday. We think it is very important that you turn in the homework assignments on time and we are unable to accept late homeworks; if you cannot complete an assignment on time, please just hand in what you are able to do.

When we grade homeworks, we will give full credit for correct answers and proofs. We will give 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 there only in the hope of getting partial credit. Please only write down answers in which you are confident. Wild guesses make life difficult for the graders. 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 (though that may preclude submitting by email).

If you are unfamiliar with LaTeX, we recommend taking one of the Athena mini-courses on LaTeX offered in February. (There are links on the course website to mini-course information as well as a useful LaTeX How-To document).

Four of the homework assignments will be half-sized. These are the ones that cover single lectures, in weeks where the other lecture slot is taken up by a quiz or a national holiday.

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

Quizzes and Exams

There will be three quizzes and one final exam. The three quizzes will be held during class time on Wednesday: February 28, April 4, and May 2. Each quiz will cover one of the three major units 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 exam will be during finals week, and has yet to be scheduled.