• Due date for HW2 is postponed to THURSDAY, September 28
  • New HW submission instructions: please include your NAME or CS LOGIN as part of the text of your submission for each problem!
  • If you have downloaded HWs prior to Sept 7, while the homework problems haven't changed, the instructions for turning in your homework have. We now plan to use provide on the EECS system to have you turn them in electronically. The new version of the hw lists the provide command to do that
  • You are expected to check the course webpage frequently. Any changes to assignments, errata, office hours, deadlines, snow days, etc. will be posted here!

Course Information

This course is intended as an introduction to the theory of computation for senior level undergraduates and graduate students looking for background material in theory. The major topics within the course include: models of computation, finite automata, regular languages, context free grammars, turing machines, undecidability, infeasibility, diagonalizations, nondeterminism, information theory, time vs space, and complexity classes.

Prerequisites: MATH/COMP 61 and COMP 15 are recommended, but any prior course with rigorous mathematical proofs should suffice

Textbook: Introduction to the Theory of Computation by Michael Sipser
ISBN: 9781133187790 (3rd Edition) or 9780534950972 (2nd Edition)
List of errata: Errata for 3rd Edition and Errata for 2nd Edition

Instructor: Lenore Cowen
Office: Room 107A Halligan Hall
Office Hours: Thursdays at 1:30pm, or email for appointment

Class Location: Robinson Hall, Room 253
Time: (Tues/Thurs) 12:00pm - 1:15pm

Email Address for Questions:

Teaching Assistants (office hours click here):
Adam Plumer
Ben Machlin
Dana Sussman
Daniel Jin
Elias Marcopoulos
Elif Ölmez
Phoebe Yu Yang