Theory of computation

Lectures: 2 sessions / week, 1.5 hours / session

Recitations: 1 session / week, 1 hour / session

Principles of Applied Mathematics (18.310C) or Mathematics for Computer Science (18.062J / 6.042J).

You need some facility with the mathematical concepts of theorem and proof. Most of the assignments in this course require proving some statement and some creativity in finding the proof will be necessary.

Sipser, Michael. Introduction to the Theory of Computation. 2nd ed. Boston, MA: Thomson Course Technology, 2006. ISBN: 0534950973.

You'll need the 2nd edition because of the new homework problems it contains. Errata for 2nd edition of textbook.

Recitations are primarily for going over lecture material in more detail, for answering questions and for reviewing homework and exams. Recitation attendance is optional, and you may attend any recitation you wish. However, if you are having trouble with the course, you will be expected to attend recitations weekly; doing so may keep you from failing. No recitations during the first week.

40% of grade. There will be 6 biweekly problem sets. Cooperation policy: Permitted (though not encouraged). If you do cooperate on some problems, then solutions must be written up individually (not copied). Using outside or online materials is not permitted. Homework is due on Thursdays by 11:00 am sharp. Late homework will be accepted the following day up to 1:00 pm, but will be charged a 1 point per problem (out of the 10 point maximum) late penalty. Homework submitted after that will not be graded but will be kept for reference.

One midterm (20% of grade) during a class session and one final exam (40% of grade) during finals week. The exams are both open book and open notes. You may only use the class textbook and notes you took in lectures and in recitation (i.e. no other books or print-outs of other courses' problems).

Don't show me this again

This is one of over 2,200 courses on OCW. Find materials for this course in the pages linked along the left.

MIT OpenCourseWare is a free & open publication of material from thousands of MIT courses, covering the entire MIT curriculum.

No enrollment or registration. Freely browse and use OCW materials at your own pace. There's no signup, and no start or end dates.

Knowledge is your reward. Use OCW to guide your own life-long learning, or to teach others. We don't offer credit or certification for using OCW.

Made for sharing. Download files for later. Send to friends and colleagues. Modify, remix, and reuse (just remember to cite OCW as the source.)

Learn more at Get Started with MIT OpenCourseWare