Great Ideas in Theoretical Computer Science
Lecture Notes
These notes were prepared by 6.089 students to fulfill their "scribe notes" requirement. All notes are courtesy of the student named in the file, and are used with permission.
|
LEC # |
TOPICS |
|
1 |
Introduction (PDF) |
|
2 |
Logic (PDF) |
|
3 |
Circuits and finite automata (PDF) |
|
4 |
Turing machines (PDF) |
|
5 |
Reducibility and Gödel (PDF) |
|
6 |
Minds and machines (PDF) |
|
7 |
Complexity (PDF) |
|
8 |
Polynomial time (PDF) |
|
9 |
P and NP (PDF) |
|
10 |
NP-completeness (PDF) |
|
11 |
NP-completeness in practice (PDF) |
|
12 |
Space complexity and more (PDF) |
|
13 |
Randomness (PDF) |
|
14 |
Probabilistic complexity classes (PDF) |
|
15 |
Derandomization / cryptography double feature (PDF) |
|
16 |
Private-key cryptography (PDF) |
|
17 |
Public-key cryptography (PDF) |
|
18 |
Cryptographic protocols (PDF) |
|
19 |
Interactive proofs / machine learning (PDF) |
|
20 |
Probably Approximately Correct (PAC) learning (PDF) |
|
21 |
Learning, Chomsky, RSA, quantum (PDF) |
|
22-23 |
Quantum computing (PDF) |
|
24 |
Quantum algorithms (PDF) |
Assignments
Problem Set 1 (PDF)
Problem Set 2 (PDF)
Problem Set 3 (PDF)
Problem Set 4 (PDF)
Problem Set 5 (PDF)