TL;DR: CS 121 is a proof-based course that requires a certain level of mathematical maturity and comfort with discrete mathematics. One good way to gain this background is via CS 20, but (especially if you took Math 23/25/55) you can also pick up these concepts via the self study program listed below. The material below is useful for CS 124 as well.
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.
The following is recommended for all students to go over as a way to prepare for the mathematical contents of CS 121:
Homework Zero ( .md source ) - this is one good tool for self assessment. The current version is the fall 2017 version. I will post the Fall 2018 version before the end of July 2018. Homework zero will be due in the first week of class.
Mathematical background chapter: Regardless of whether you took CS 20 or other proof-based courses, you should read the Mathematical background chapter (pdf version , see also html version) of the CS 121 text before the term begins.
I also recommend you read the preface and Introduction notes before the first lecture.
You might find the following student feedback on required background useful but keep in mind that each person is different and so “your milage may vary”.
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 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. The time to work over this material can vary considerably depending on your background, but you should start early to allow yourself at least 40 hours to do so. THe plan below uses 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 that were used in CS 20 until recently. I don’t know of official solutions to the problem sets, but it seems some solutions are available online.
The following notions are the ones that are most crucial for CS 121, as well as other theoretical CS courses such as CS 124:
Since proofs are so important, if you have not had experience with proofs, I suggest complementing the above with some additional reading. I’ve heard good things about the book How to read and do proofs by Daniel Solow as an introductions to proofs for people with no prior exposure.
There are also some nice handouts from other courses. Stanford’s CS 103 class has a nice set of handouts on proofs, mathematical vocbulary, indirect proofs, and proof writing checklist. This writeup by Hutching is also a good read.
Proofs by induction or “well ordering”: Induction is a tool that is often used in the analysis of algorithms but people (myself included!) initially find it quite 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” of mathematics 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 (but highly recommended) 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
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 second half of this course we will use discrete probability rather extensively. We will do a quick introduction to the concepts we need (which will be mostly the notions of events, random variables, expectation, and concentration over finite sample spaces), see the probability chapter from the CS 121 text. However, if you have not taken (or planning to take this term) STAT 110 or a similar course, you can benefit from watching this lecture, reading chapters 17-20, and doing Homework 10 and Homework 11.
For additional material on probability, 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.