Great Ideas in Theoretical Computer Science

Course Description

This course provides a challenging introduction to some of the central ideas of theoretical computer science. It attempts to present a vision of "computer science beyond computers": that is, CS as a set of mathematical tools for understanding complex systems such as universes and minds. Beginning in antiquity—with Euclid's algorithm and other ancient examples of computational thinking—the course will progress rapidly through propositional logic, Turing machines and computability, finite automata, Gödel's theorems, efficient algorithms and reducibility, NP-completeness, the P versus NP problem, decision trees and other concrete computational models, the power of randomness, cryptography and one-way functions, computational theories of learning, interactive proofs, and quantum computing and the physical limits of computation. Class participation is essential, as the class will include discussion and debate about the implications of many of these ideas.

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)

No comments: