Great Ideas in Theoretical Computer Science >> Content Detail

Lecture Notes

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.

1Introduction (PDF)
2Logic (PDF)
3Circuits and finite automata (PDF)
4Turing machines (PDF)
5Reducibility and Gödel (PDF)
6Minds and machines (PDF)
7Complexity (PDF)
8Polynomial time (PDF)
9P and NP (PDF)
10NP-completeness (PDF)
11NP-completeness in practice (PDF)
12Space complexity and more (PDF)
13Randomness (PDF)
14Probabilistic complexity classes (PDF)
15Derandomization / cryptography double feature (PDF)
16Private-key cryptography (PDF)
17Public-key cryptography (PDF)
18Cryptographic protocols (PDF)
19Interactive proofs / machine learning (PDF)
20Probably Approximately Correct (PAC) learning (PDF)
21Learning, Chomsky, RSA, quantum (PDF)
22-23Quantum computing (PDF)
24Quantum algorithms (PDF)


© 2009-2020, All Rights Reserved.
Higher Ed Space ® is a registered trademark of AmeriCareers LLC.