Calendar

LEC # TOPICS KEY DATES
1 Introduction  
2 Logic  
3 Circuits and finite automata Problem set 1 assigned
4 Turing machines  
5 Reducibility and Gödel  
6 Minds and machines  
7 Complexity

Problem set 1 due

Problem set 2 assigned

8 Polynomial time  
9 P and NP  
10 NP-completeness  
11 NP-completeness in practice

Problem set 2 due

Problem set 3 assigned

12 Space complexity and more  
13 Randomness Problem set 3 due
14 Probabilistic complexity classes  
  In-class midterm  
15 Derandomization / cryptography double feature  
16 Private-key cryptography Problem set 4 assigned
17 Public-key cryptography  
18 Cryptographic protocols  
19 Interactive proofs / machine learning Problem set 4 due
20 Probably Approximately Correct (PAC) learning Problem set 5 assigned
21 Learning, Chomsky, RSA, quantum  
22-23 Quantum computing  
24 Quantum algorithms Problem set 5 due