Automata, Computability, and Complexity
Lecture Notes
|
LEC # |
TOPICS |
LECTURE NOTES |
|
1 |
Introduction |
(PDF) |
|
2 |
Logic, circuits, and gates |
(PDF) |
|
3 |
Deterministic finite automata (DFAs) and nondeterministic finite automata (NFAs) |
(PDF) |
|
4 |
NFAs and regular expressions |
(PDF) |
|
5 |
Non-regular languages and the pumping lemma |
(PDF) |
|
6 |
Turing machines |
(PDF) |
|
7 |
Decidability |
(PDF) |
|
8 |
Undecidable problems and Post correspondence problem (PCP) |
(PDF) |
|
9 |
Mapping reducibility and Rice's theorem |
(PDF) |
|
10 |
Self-reference and the recursion theorem |
(PDF) |
|
11 |
Introduction to cryptography |
(PDF) |
|
12 |
Complexity theory |
(PDF) |
|
13 |
Pseudorandom generators and one-way functions |
(PDF) |
|
14 |
Public-key cryptography |
(PDF) |
|
15 |
More complexity theory |
(PDF) |
|
16 |
More NP-completeness |
(PDF) |
|
17 |
Probabilistic Turing machines and complexity classes |
(PDF) |
|
18 |
Trapdoor one-way functions and zero-knowledge proofs |
(PDF) |
|
19 |
Probably approximately correct (PAC) learning |
(PDF) |
|
20 |
More PAC learning |
(PDF) |
|
21 |
Introduction to quantum |
(PDF) |
|
22 |
Quantum mechanics and BQP |
(PDF) |
|
23 |
Quantum algorithms |
(PDF) |
Cryptography Handout
Introduction to cryptography and RSA (PDF) (Courtesy of Leonid Grinberg. Used with permission.)
Assignments
|
TOPICS |
PROBLEM SETS |
|
Problem set 1: Number theory and regular languages |
(PDF) |
|
Problem set 2: Context-free languages |
(PDF) |
|
Problem set 3: The Gödel-Turing mindblower |
(PDF) |
|
Problem set 4: Computability and complexity |
(PDF) |
|
Problem set 5: NP-completeness and more |
(PDF) |
|
Problem set 6: Randomness and cryptography |
(PDF) |