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

TuringGodel

Overview:

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?

Staff: 

Professor: Aaron Roth
TAs: Nimit Singhania (Head TA), Lingbin Cai, Jonathan Chen, Meryem Essaidi, Jake Hart, Rohit Kothur

Logistics:

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  -- Non-regular languages and the pumping lemma (9/23)
  9. Lecture  -- Begin Turing machines (9/25)
  10. Lecture  -- Continue Turing machines (9/30)
  11. Lecture  -- More Turing machines... (10/2)
  12. Lecture  -- Equivalence of Turing machines and enumerators, and the decidability of DFA equivalence (10/7)
  13. Midterm  -- In Fagin Hall(10/14)
  14. Lecture  -- Uncountability of the reals, and existence of undecidable problems (10/16)
  15. Lecture  -- The halting problem, and reductions. (10/21)
  16. Lecture  -- More undecidable problems. Reductions in Computability (10/23)
  17. Lecture  -- More Reductions (10/28)
  18. Lecture  -- Information, Randomness, and Compression: Kolmogorov Complexity (10/30)
  19. Lecture  -- Godel's incompleteness theorem (11/4)
  20. Lecture  -- Begin time complexity: P and NP (11/6)
  21. Lecture  -- NP hardness and completeness, and polynomial time reductions (11/11)
  22. Lecture  -- Cook's Theorem: SAT is NP Complete (11/13)
  23. Lecture  -- NP Completeness of CLIQUE, INDEPENDENT-SET, VERTEX-COVER, and HAMILTONINAN-PATH (11/17)
  24. Lecture  -- Approximation Algorithms (11/21)
  25. Lecture  -- Advanced Topics (Randomness) (11/24)
  26. Lecture  -- Advanced Topics (PSPACE) (11/28)
  27. Lecture  -- Advanced Topics Public Key Cryptography (12/4)
  28. Last Class -- The power of algorithms! (12/9)
  29. Final Exam  -- (TENTATIVE DATE) (12/15 12:00-2:00)

Assignments:

  1. Problem Set 1. Due 9/9/14.
  2. Problem Set 2. Due 9/23/14.

Office Hours: