This course seeks to answer the big, deep, theoretical questions about computers: what can they do and how efficiently can they do it? We'll study several theoretical models of computing, culminating in Turing machines. The course touches on a lot of important questions, including several that remain unanswered. Along the way we'll see a lot of cool proofs and a variety of connections to other areas.

Textbook: Introduction to the Theory of Computation by Michael Sipser, 2nd ed.
Syllabus: Download here
Office hours: Mon. 2-3 and 4-5, Wed. 10-11, Thur. 11-12, Fri. 2-3 (or by appointment)

Homeworks

Homework 1, Due Sept. 11

Homework 2, Due Sept. 18, Bonus #1 complete

Homework 3, Due Sept. 25, Bonus #1 complete

Homework 4, Due Oct. 2, Bonus #1 complete

Homework 5, Due Oct. 9, Bonus #1 complete

Homework 6, Due Oct. 14, Bonus #1 complete

Homework 7, Due Oct. 30, Bonus #1 complete

Homework 8, Due Nov. 6

Homework 9, Due Nov. 13, Bonus #1 complete

Homework 10, Due Nov. 23