Welcome to CS46: Theory of Computation! Computer technology changes rapidly, but the underlying model of computation is relatively unchanged since 1960. How do computers compute, and why is this method of computation preferred over other methods? Why, for instance, do modern computers have a notion of volatile memory. Is this a requirement or a convenience for computation? Do other methods of computatation even exist? Could we solve more interesting problems with another model? Could we solve the same problems we solve today using a simpler model of computation? In this course will will look at various theoretical models of computation and examine the computational power of these models. For each model we consider problems that can and cannot be solved, and develop a rigorous method of classifying how difficult certain problems are to compute. While the course emphasis is on theory, there are many applications of the topics discussed. Regular expressions, compilers, CPU job scheduling, and many other realworld problems have some underlying computational model rooted in the theory of computation.
Throughout this course, we will develop mathematical concepts which are fundamentally important for computer science: decidability, undecidability, and computational complexity. We will be able to go beyond simply saying "this problem seems hard" and show that some computatational problems are inherently harder than others or simply unsolvable by a wide range of computational models. In this manner, the course explores the limits of computers and computation. Sadly (or perhaps thankfully), computers cannot solve everything efficiently.
Course Basics
Lecture: 
Tue./Thu. 9:55AM11:10AM, Science Center 181 
Lab A: 
Thursday 1:05PM  2:35PM, Science Center 240 
Lab B: 
Thursday 2:45PM  4:15PM, Science Center 240 
Instructor: 
Andrew Danner 
Textbook: 
Introduction to the Theory of Computation, Third
Edition by Sipser.
Errata.

Email: 
adanner at cs dot swarthmore.edu 
Office: 
Science Center 247 
Office Hours: 
Mon: 10amnoon Wed: 1pm3pm and by appointment 
Lab Assignments: 
weekly, due Wednesday 11:59PM 
Course Discussion: 
Piazza (by invitation, mandatory enrollment) 
Clickers
This course will use clickers to facilitate feedback, discussion, and student evaluation during class. For many upper level courses including CS46, we are now requiring that students purchase their own clicker for personal use. Please see the
department clicker page for purchasing and registering information.
Additional references