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

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. Reading this book over the summer can be a pleasant way to prepare for the course. Another fun summer read which is good for math backgroudn in general (and not just specific to this course) is the book How not to be wrong by Jordan Ellenberg.

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 good accompaniment for the first half or so 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).

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.

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**Discrete probability:**In the later part of this course we will use*discrete probability*rather extensively. We will do a quick introductions to the concepts we need (which will be mostly the notions of*events*,*random variables*,*expectation*, and*concentration*over finite sample spaces). If you have not taken STAT 110 or a similar course, you might want to watch this lecture and read these lecture notes.