Note: this page was used for MATH387 in the Fall 2014 semester. For current classes, follow the "Teaching" link on the left.

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. 9-11, Wed. 3-4, Thur. 10-11, Fri. 10-11 (or by appointment)

Homeworks

Homework 1, Due Sept. 12

Homework 2, Due Sept. 19

Homework 3, Due Sept. 26

Homework 4, Due Oct. 17

Homework 5, Due Nov. 3

Homework 6, Due Nov. 10

Homework 7, Due Nov. 26