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