CS-121 / CSCI-E121: Introduction to Theoretical Computer Science

syllabus - schedule - piazza - canvas - gradescope background - lectures - nand pl

NEWS:

Computation occurs over a variety of substrates including silicon, neurons, DNA, the stock market, bee colonies and many others. In this course we will study the fundamental capabilities and limitations of computation, including the phenomenon of universality and the duality of code and data. Some of the questions we will touch upon include: Are there functions that cannot be computed? Are there true mathematical statements that can’t be proven? Are there encryption schemes that can’t be broken? Is randomness ever useful for computing? Can we use the quirks of quantum mechanics to speed up computation?

For a high level overview of much of what we’ll see in this course, you could do far worse than read Bernard Chazelle’s wonderful essay on the Algorithm as an Idiom of modern science.

This course will have very extensive lecture notes but no official textbook. However, the following books can be helpful:

See the background page for some useful resources on the mathematical background.