6.080  Great Ideas in Theoretical Computer Science

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.

Prerequisites. This course is designed for undergraduates (both under- and upperclassmen) in computer science and related areas of science and engineering. Others (including graduate students) are welcome to take the course but might wish to discuss with the instructor. There are no formal prerequisites. The only prerequisite is some facility with mathematical reasoning: that is, the ability to construct valid mathematical arguments (including proofs by contradiction, induction, etc.) and to recognize errors in invalid ones. Such facility might be gained, for example, by taking 6.042. Programming experience is helpful but not essential; the course has no programming assignments.

Relation to other courses. There is significant overlap between 6.080 and 6.045. The main difference is that 6.080 is an experimental course, which presents many ideas normally postponed until graduate courses, whereas 6.045 provides a more traditional introduction to computability, formal languages, and complexity theory. Students who seek a solid grounding in formal languages, suitable for further work, are advised to take 6.045, whereas those wishing to learn about recent insights in theoretical computer science might prefer 6.080. There is also significant overlap between 6.080 and 6.840. However, as a graduate course, 6.840 is able to cover topics in much more mathematical depth. It is hoped that many students taking 6.080 will go on to take 6.840. The overlap between 6.080 and 6.006 (or 6.046) is smaller.

Please see the syllabus for more information.