Aaronson's MIT lectures on theoretical computer science - open to all

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.

Scott writes on his blog, Shtetl-optimized, where he's created blogthread for the course, including links to completed lectures:

• 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.