CIS 262: Automata, Computability, and Complexity



In this class we will be learning about the mathematical science behind Computer Science -- the study of what things can and cannot be computed even in principle. We will start by considering a very simple model of computation -- the finite automaton. This model captures what can be computed in finite memory, but is already surprisingly powerful -- as we will see, it is sufficient to capture regular languages. This model will give us our first taste of how to reason about the limitations of computation. We will then study a much more powerful model of computation, the Turing machine, which captures (as far as we know) the power to compute anything that we can compute by physical means, by any method. Surprisingly, we will see that this model of computation still has dramatic, fundamental limitations. Finally, we will consider the question of computation with limited resources. What can we compute subject to the constraint that the running time of our algorithm must be polynomial in the size of the input (the complexity class P)? What is the power of non-determinism (the complexity class NP)? How can we cope with these limitations, if they apply to problems that we need to solve?


Professor: Aaron Roth
TAs: Matthew Joseph (Head TA), Eric Kwong, He Chen, Justin Austin, Kelly Tan, Lucy Chai, Meryem Essaidi, Omar Paladines, Paul Lou, Vivek Raj


Class Time and Location: Tuesday/Thursday 12:00-1:30, Towne 100
Recitation: Monday 4:30-5:30 DRLB A1
Prerequisites: CIS 160 and mathematical maturity.
Course Software: We will be using Piazza for questions. Ask and answer questions here (this counts towards your participation grade). You will turn in assignments and see grades using GradeScope (Course entry code: 9RDNR9).
Textbook: Introduction to the Theory of Computation (3rd Edition), by Michael Sipser.

Problem Sets

  1. Problem Set 1. Due September 8th by 11:59am.
  2. Problem Set 2. Due September 27 by 11:59am.
  3. Problem Set 3. Due October 11 by 11:59am.
  4. Problem Set 4. Due November 1 by 11:59am.
  5. Problem Set 5. Due November 17 by 11:59am.
  6. Problem Set 6. Due December 6 by 11:59am.

Lecture Slides:

  1. Lecture 1
  2. Lecture 2
  3. Lecture 3
  4. Lecture 4
  5. Lecture 5
  6. Lecture 6
  7. Lecture 7
  8. Lecture 8
  9. Lecture 9
  10. Lecture 10
  11. Lecture 11
  12. Lecture 12
  13. MIDTERM (10/13)
  14. Lecture 13
  15. Lecture 14
  16. Lecture 15
  17. NO CLASS (10/27)
  18. Lecture 16
  19. Lecture 17
  20. Lecture 18
  21. NO CLASS (11/10)
  22. Lecture 19
  23. Lecture 20
  24. Lecture 21
  25. Lecture 22
  26. Lecture 23
  27. Lecture 24 --- Last class!
  28. FINAL EXAM: Tuesday, December 20, 12:00-2:00. Meyerson Hall B1.

Office Hours: