CIS 262: Automata, Computability, and Complexity

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 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?

Staff: 

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

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 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.


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 -- Decidable and Recognizable Languages + Variants on Turing Machines (10/4)
  12. Lecture 12 -- Closure properties of Decidable/Recognizable languages (10/11)
  13. MIDTERM (10/13)
  14. Lecture 13 -- Undecidable Problems (10/18)
  15. Lecture 14 -- Unrecognizable problems (10/20)
  16. Lecture 15 -- Reductions (10/25)
  17. Lecture 16 -- Linear Bounded Automata (10/27)
  18. Lecture 17 -- Kolmogorov Complexity (11/1)
  19. Lecture 18 -- Begin time complexity; the class P. (11/3)
  20. Lecture 19 -- Non-determinisim, and the class NP. (11/8)
  21. NO CLASS (11/10)
  22. Lecture 20 -- NP Completeness and reductions. (11/15)
  23. Lecture 21 -- More reductions; Cook's Theorem. (11/17)
  24. Lecture 22 -- Approximation Algorithms. (11/22)
  25. Lecture 23 -- Randomized Algorithms. (11/29)
  26. Lecture 24 -- Advanced Topics (12/1)
  27. Lecture 25 -- Advanced Topics (12/6)
  28. Lecture 26 -- Review -- Last class! (12/8)

Office Hours: