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

Primary Textbook: Introduction to the Theory of Computation by Michael Sipser
Other Reading: Gödel's Proof by Ernest Nagel and James Newman
Other Reading: The Annotated Turing by Charles Petzold

Instructor: Megan Monroe
Email: megan.monroe@tufts.edu
Office: Joyce Cummings Center, Room 440D
Office Hours: Wednesday, 1:30-3:30pm

Class Location: Joyce Cummings Center, Room 270
Time: (Tues/Thurs) 1:30 - 2:45am
Final Exam: Monday, May 5th, 3:30-5:30pm

Course Piazza: CS170 Spring 2025

Teaching Fellows:
Noah Bell
Doga Kilinc
Teddy Schneider