Textbook and Readings

Textbook: Michael Sipser. Introduction to the Theory of Computation. Cengage Learning, 3rd edition, 2013. The university bookstore carries this book, which is a required textbook for this course.

Readings: This list will change as we progress through the semester, based on student interests and classroom discussions.

Pam A. Mueller and Daniel M. Oppenheimer. The pen is mightier than the keyboard: Advantages of longhand over laptop note taking. Psychological Science, 25(6):1159–1168, 2014. PMID: 24760141.
Ken Thompson. Reflections on trusting trust. Communications of the ACM, 27(8):761–763, August 1984.
Lov K. Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the 28th Annual ACM Symposium on the Theory of Computing (STOC), pages 212–219, Philadelphia, PA, May 1996.
Julia Chuzhoy, David H. K. Kim, and Rachit Nimavat. New hardness results for routing on disjoint paths. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, pages 86–99, New York, NY, USA, 2017. ACM.