MIT EECS - Subject Description

MIT EECS Subject

Spring 2008

6.080 Great Ideas in Theoretical Computer Science . . . Description
Undergraduate
Prereq: mathematical maturity at the calculus level will be expected and programming experience helpful
Units: 3-0-6
Schedule: L TR2:30-4, room 32-155
Staff: Professor Scott Aaronson

Description

This course is for freshmen and sophomores who seek a challenging overview of the theoretical ideas underlying modern computer science. Topics include finite automata; propositional logic; Turing machines and undecidability; the Church-Turing Thesis; Godel's completeness and incompleteness theorems; efficient algorithms; reductions and completeness; the P versus NP problem; circuit complexity; randomized algorithms; cryptography and one-way functions; pseudorandom generators; zero-knowledge and interactive proofs; and quantum computing.

Meets with 6.089.