### 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):

- Lecture 1: Overview. Introduction to finite automata. Sipser 1.1. (8/28)
- Lecture -- Designing finite automata, formal definition of computation (9/2)
- Lecture -- Regular operations and closure under union. Begin non-determinism (9/4)
- Lecture -- Equivalence between NFAs + DFAs, closure under regular operations. (9/9)
- Lecture -- Regular Expressions and equivalence with regular languages (9/11)
- Lecture -- Non-regular languages and the pumping lemma (9/16)
- Lecture -- Begin Turing machines (9/18)
- Lecture -- Continue Turing machines (9/23)
- Lecture -- More Turing machines... (9/25)
- Lecture -- Equivalence of Turing machines and enumerators, and the decidability of DFA equivalence (9/30)
- Midterm -- (TENTATIVE DATE) (10/2)
- Lecture -- Uncountability of the reals, and existence of undecidable problems (10/7)
- Lecture -- The halting problem, and reductions. (10/14)
- Lecture -- More undecidable problems. Reductions in Computability (10/16)
- Lecture -- More Reductions (10/21)
- Lecture -- Information, Randomness, and Compression: Kolmogorov Complexity (10/23)
- Lecture -- Godel's incompleteness theorem (10/28)
- Lecture -- Begin time complexity: P and NP (10/30)
- Lecture -- NP hardness and completeness, and polynomial time reductions (11/4)
- Lecture -- Cook's Theorem: SAT is NP Complete (11/6)
- Lecture -- NP Completeness of CLIQUE, INDEPENDENT-SET, VERTEX-COVER, and HAMILTONINAN-PATH (11/1)
- Lecture -- Approximation Algorithms (11/13)
- Lecture -- Advanced Topics (Randomness) (11/17)
- Lecture -- Advanced Topics (PSPACE) (11/21)
- Lecture -- Advanced Topics (Interactive Proofs) (11/24)
- Lecture -- Advanced Topics IP = PSPACE(12/2)
- Lecture -- Advanced Topics Public Key Cryptography (12/4)
- Last Class -- The power of algorithms! (12/9)
- Final Exam -- (TENTATIVE DATE) (12/15 12:00-2:00)

### Office Hours: