Introduction to Theoretical Computer Science

The Fall 2017 offering of this course will be significantly revised from previous iterations. Please check this page on August 2017 for updated information. In particular I will post on this page a homework zero that you should complete before the first lecture.

See this page for information on being a Teaching Fellow in CS 121.

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?

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

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.

Prerequisites

CS 121 expects students to have “experience in formal mathematics at the level of CS 20”. The main requirement is the ability to read, write (and hopefully even enjoy!) mathematical proofs, as well as comfort with (or the ability to pick up) notions from discrete mathematics such as sets, functions, logical operators, asymptotic growth, discrete probability and graphs.

If you have not taken Math 23, Math 25, or Math 55, please assess yourself by taking the CS 20 placement test. If you do not find the majority of the questions easy, you should probably take CS 20 before taking CS 121. If you are not sure if you have the background to take CS 121, or want advice how to prepare for the course, please email me (Boaz Barak) and I will be happy to discuss this with you.

Preparation via self study

If you don’t have significant experience and comfort with mathematical proofs, have not taken Math 23/25/55, and don’t find the above placement test easy, then I do recommend you take CS 20 before CS 121. But if it’s not possible for you to take CS 20, or if you feel confident enough about your math skills that you prefer to skip CS 20, it is possible to pick up the required background for CS 121 via self study.

There are a number of great resources available on the web for the mathematical notions we’ll need, but below is a concrete suggestion of how to catch up on the most essential background that would be useful for CS 121.

A great resource for this material is the MIT course 6.042j Mathematics for Computer science whose lectures videos, transcripts, and exercises are available online. This course has a very extensive set of lecture notes by Lehman, Leighton and Meyer (henceforth “LLM”) and a previous version by Lehman and Leighton (henceforth “LL”). (These lecture notes are also the ones used in CS 20.)

The following notions are the most crucial for CS 121: