While the formal prerequisites have not changed, CS 121 is undergoing a significant revision in Fall 2017. This makes it even more important this term that you have a basic comfort with mathematical proofs and the concepts of discrete mathematics. To assess yourself, please complete Homework Zero before the first lecture, or by Wednesday, September 6th.
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. See below for more discussion on these topics, as well as advice on how to catch up on them.
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, see below.
The mathamatical background section of the lecture notes contains a brief overview of some of the mathematical notions we will use. There are a number of great resources available on the web to catch up on those. Some example include the Lehman-Leighton-Meyer notes we discuss below, Jim Aspnes’ online available book Notes on Discrete Mathematics the lecture notes for Berkeley CS 70 and the book by Rosen (which has a freely available version online).
Below is a concrete suggestion of how to catch up on the most essential background that would be useful for CS 121 using 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: Mathematical proofs are by far the most important notion you need to get comfortable with. Read Chapter 1 (pages 3-28) from LLM, watch Lecture 1 and do Homework 1. This handout of Hutching is also a good read, as well the following handouts on proofs, mathematical vocbulary, indirect proofs, and proof writing checklist from Stanford’s cs 103 class. Finally, if you have not taken a proof-based course before, you might want to also get the book How to read and do proofs by Daniel Solow
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 Chapter 4 (pages 97-129) from LLM and do from that chapter Problem 4.8, Problem 4.13, Problem 4.14, Problem 4.18, Problem 4.25, Problem 4.31, and Problem 4.37. 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 (for more depth. you can read Chapters 10-12 in LLM), watch Lecture 6, and do Homework 4
Sums and asymptotics: 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 Chapter 14.7 (pages 588-594) from LLM, watch Lecture 12 and Lecture 13 and do Homework 7
Discrete probability: In the second half 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 (or planning to take this term) STAT 110 or a similar course, watch this lecture and read these chapters 17-20, and do Homework 10 and Homework 11. See also notes 13 till 18 of Berkeley CS 70. You might also find these notes from Stanford CS229 or this book useful. Note that we will not use probability until we’re halfway through the course, so you can defer going over this material till later. However, probability is an extremely useful topic, not just for CS 121 but also for algorithms, machine learning, and essentially any form of quantitative reasoning. Moreover the human brain is not well designed for probabilistic reasoning , and it can take time to develop good intuitions for it. So, starting early is always a good thing.