Great Ideas in Theoretical Computer Science
MIT OpenCourseWare offers this introduction to theoretical computer science framed as a set of mathematical tools for understanding complex systems, not just machines. The course moves from Euclid's algorithm and ancient computational thinking through propositional logic, Turing machines, computability, finite automata, and Godel's incompleteness theorems. It continues into efficient algorithms, reducibility, NP-completeness, the P versus NP problem, decision trees, randomness in computation, cryptography and one-way functions, computational learning theory, interactive proofs, and quantum computing's physical limits. Materials include lecture notes and assignments from MIT's course, with class discussion and debate built into the original format around the philosophical implications of these results. No prior computer science background is assumed, though the pace is described as challenging. Free to audit through MIT OpenCourseWare, with no certificate offered.