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 real-world 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:55AM-11: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: 10am-noon
Wed: 1pm-3pm
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