CIS 262: Automata, Computability, and Complexity (Fall 2014)



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 algortihm 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: Nimit Singhania (Head TA), Lingbin Cai, Jonathan Chen, Meryem Essaidi, Jake Hart, Rohit Kothur


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 can turn in assignments and see grades using Canvas.
Textbook: Introduction to the Theory of Computation (3rd Edition), by Michael Sipser.

Lectures and Exams (Rough Outline):

  1. Lecture 1: Overview. Introduction to finite automata. Sipser 1.1. (8/28)
  2. Lecture 2: More examples of finite automata, and formal definitions of acceptance, languages, and regular languages. Sipser 1.1 (9/2)
  3. Lecture 3: Definition of regular operations + proof of closure under union. Introduction to non-determinism. Sipser 1.1, 1.2. (9/4)
  4. Lecture 4: Formal definition of NFAs and Equivalence between NFAs + DFAs. Sipser 1.2 (9/9)
  5. Lecture 5: Closure under the regular operations. Sipser 1.2 (9/11)
  6. Lecture 6: Regular Expressions and equivalence with regular languages. Sipser 1.3 (9/16)
  7. Lecture 7: Finish equivalence of regular expressions and regular languages. Sipser 1.3 (9/18)
  8. Lecture 8: Non-regular languages and the pumping lemma. Sipser 1.4 (9/23)
  9. Lecture 9: More pumping lemma examples, begin Turing machines. Sipser 1.4, 3.1(9/25)
  10. Lecture 10: Formal definition of Turing Machines. Sipser 3.1 (9/30)
  11. Lecture 11: More Turing machine constructions... Sipser 3.1 (10/2)
  12. Lecture 12: Equivalence of Turing Machines and Multi-Tape Turing machines. Decidability of several easy languages. Sipser 3.2, 3.3 (10/7)
  13. Midterm  -- In Fagin Hall(10/14)
  14. Lecture 13: Uncountability of the reals, and existence of non Turing Recognizable problems Sipser 4.2 (10/16).
  15. Lecture 14: Undecidability of A_TM and the Halting problem. Definition of co-Turing-Recognizability. Sipser 4.2, 5.1 (10/21)
  16. Lecture 15: Undecidability of E_TM and Regular_TM, statement of Rice's theorem. Sipser 5.1 (10/23)
  17. Lecture 16: More Reductions (10/28) Sipser 5.1
  18. Lecture 17: Linear Bounded Automata and Mapping Reducibility. Sipser 5.1, 5.3(10/30)
  19. Lecture 18: Information, Randomness, and Compression: Kolmogorov Complexity. Sipser 6.4 (11/4)
  20. Lecture 19: Kolmogorov complexity is not computable, and Godel's incompleteness theorem via Kolmogorov Complexity. (Not in Sipser) (11/6)
  21. Lecture 20: Begin time complexity: Definitions of P and NP, robustness of the model. Sipser 7.1 (11/11)
  22. Lecture 21: Equivalence of 2 definitions of NP. How to show problems are in NP. Sipser 7.3 (11/13)
  23. Lecture 22: Formal definition of NP completeness and polynomial time reducibility. Sipser 7.4 (11/18)
  24. Lecture 23: Reductions -- NP Completeness of CLIQUE, INDEPENDENT-SET, VERTEX-COVER, and HAMILTONINAN-PATH. Sipser 7.5 (11/20)
  25. Lecture 24: Cook's Theorem. Sipser 7.4 (11/25)
  26. Lecture 25: Approximation Algorithms. Sipser 10.1 and extra material. (12/2)
  27. Lecture 26: Randomized algorithms, 2SAT, and random walks. Not in Sipser. (12/4)
  28. Lecture 27: Last class -- The amazing weighted majority algorithm. Not in Sipser. (12/9)
  29. Final Exam: Monday 12/15 12:00-2:00 in DRLB A1, A8


  1. Problem Set 1. Due 9/9/14.
  2. Problem Set 2. Due 9/23/14.
  3. Problem Set 3. Due 10/7/14.
  4. Problem Set 4. Due 11/4/14.
  5. Problem Set 5. Due 11/18/14.
  6. Problem Set 6. Due 12/4/14.

Office Hours: