Fall 2017. Schedule: TBD
Instructor: Boaz Barak
The Fall 2017 offering of this course will be significantly revised from previous iterations. Please check this page on August 2017 for updated information.
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: There is no official textbook for this course, but the following books will be helpful (and are a good read regardless):
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.
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:
Proofs by induction or “well ordering”: This is a tool we’ll use time and again and is often initially confusing; indeed when you first encounter induction it might not be clear it isn’t a “magical chant” that can allow you to prove anything. Read pages 23-42 from LL, watch Lecture 2 and Lecture 3 and do Homework 2
Sets, functions, relations: These are the basic “data types” that we will use time and again. Read pages 69-88 from LLM and do the exercises there. Optionally read also about infinite sets in the next chapter.
Sums and asymptotic: Asymptotic notation such as “Big Oh”, “Little Oh”, “Big Omega” and their relatives are theorists’ best friends. We will certainly use them very extensively in CS 121. Read pages 421-477 from LLM, watch Lecture 12 and Lecture 13 and do Homework 7
These are the basic topics that would be helpful in preparing for CS 121. MIT 6.042j (and CS 20) covers additional material that can be quite helpful, not just in CS 121 but other CS courses (and beyond). In particular, if you have not taken Stat 110 or a similar course, you might want to brush up on discrete probability though we will only use it toward the end of CS 121, and that point hopefully you’d be able to pick it up on your own.