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):

- Quantum Computing Since Democritus / Aaronson. This book offers a freeflowing 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.
- 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.
- 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 a very good accompainment for the first half or so of the course.

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:

**Mathematical proofs:**This is by far the most important notion you need to get comfortable with. Read pages 3-23 from LLM, watch Lecture 1 and do Homework 1.**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.**Graphs:**These are also extremely important in computer science and our course is no exception. Read pages 73-87 from LL, watch Lecture 6, and do Homework 4**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**Asymptotics of recurrences:**We often want to analyze the asymptotic running time of recursive algorithms. Read pages 142-158 of LL, watch Lecture 14 and do Homework 8

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.