Course Information: Computation Theory

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, time and space, and complexity classes.

Class information: Details of COMP 170 can be found in a number of places:

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 J. Cowen
Email: cowen AT
Office: Working remotely (no on-campus office).
Office Hours: Tuesdays from 9:15-10:15am (excluding Feb 2); Wednesdays at 4:15-5:15pm in sococo, or find the direct zoom link on canvas/piazza. Or email for an appointment if neither time is good.

Class Location: Online. Zoom link is but requires a password, available from the Canvas course site, or join Piazza for instructions on how to obtain it if you can' get it from Canvas.

Section zoom links are also available on canvas

Time: Tuesdays and Thursdays, noon – 1:15 PM

Teaching Assistants:
Section A: Derek Egolf (TF), Ana Arsovska, Conrad Walsh, Patrick Gavazzi.
Section B: Andrew Gonczi (Head TA), Thomas Chang-Davidson, Collin Geary, Owen Morrissey
Section C: Riley Price, Aditi Kocherlakota, Abby Larson
Section D: Charles Oddleifson, Claudia Aranda Barrios, Conor Gourley, Alexndra Scott
Section E: Yuye Jiang, Athokshay Ashok, Lily Zhang, Aaron Schneidereit
TA: Office Hours: See course piazza page for TA office hours and links starting in the 2nd week of classes.