Scott Aaronson teaches an MIT course on theoretical computer science (emphasis mine)
6.080 Great Ideas in Theoretical Computer Science
... 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 m achines 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...
Prerequisites. This course is designed for undergraduates (both under- and upperclassmen) in computer science and related areas of science and engineering.... The only prerequisite is some facility with mathematical reasoning ... Programming experience is helpful but not essential; the course has no programming assignments.
- Lecture 1: Introduction
- Lecture 2: Logic
- Lecture 3: Circuits and Finite Automata
- Lecture 4: Turing Machines
- Lecture 5: Reducibility and Gödel
- Lecture 6: Minds and Machines
- Lecture 7: Complexity
- Lecture 8: Polynomial Time
- Lecture 9: P and NP
- Lecture 10: NP-completeness
- Lecture 11: NP-completeness in Practice
- Lecture 12: Space Complexity and More
- Lecture 13: Randomness
- Lecture 14: Probabilistic Complexity Classes
- Lecture 15: Derandomization / Crypto Double Feature
- Lecture 16: Private-Key Cryptography
- Lecture 17: Public-Key Cryptography
- Lecture 18: Cryptographic Protocols (including: how computer scientists date!)
- Lecture 19: Interactive Proofs / Machine Learning
A typical lecture handout is about 8 pages. I plan to print out each one and leave them by the spot where I keep all the material for five minutes of concentrated attention is practical.
Amidst the mixed news of everyday life in 2008, what a wonder it is that all of us can freely share in work like this. Thank you Scott, and thank you MIT.