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

This is the webpage for the Fall 2018 offering of this course.

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


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.

The textbook for this course is Introduction to Theoretical Computer Science / Boaz Barak, which is a book in preparation that is available freely online.

In addition the following books can be helpful:

  • Quantum Computing Since Democritus / Aaronson. This book offers a free-flowing overview of many of the topics we will cover in this course (as well as several we won’t), and is an easy (and often entertaining) read. Reading this book over the summer can be a pleasant way to prepare for the course. From the back cover: “I laughed, I cried, I fell off my chair - and that was just reading the chapter on computational complexity.”, Seth Lloyd, MIT.

  • Other summer reading suggestions: Though not directly related to this course, another fun summer read which is good for math background in general (and not just specific to this course) is the book How not to be wrong by Jordan Ellenberg. Yet another very short but highly recommended general math book is Mathematics: A very short introduction by Timothy Gowers.

  • The nature of computation / Moore and Mertens. This monster (900+ pages) of a book contains a wealth of information on computation from a unique perspective. While reading it cover to cover is a large undertaking, it is a great book to sample from and have by your side as a reference (or as a makeshift monitor stand).

  • Introduction to the theory of Computation / Sipser. This was the textbook for CS121 in previous iterations. It is an extremely well-written book with very clear explanations and proofs, and can serve as a good accompaniment for about half of this course.

  • Computational complexity: A modern approach / Arora and Barak. This is a graduate textbook on computational complexity, and hence contains much more than what we’ll cover here. However, it might serve as a useful reference for some of the topics of this course (especially in its second half).

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