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, you can asses yourself by taking the following CS 20 placement test or by attempting our Homework Zero. If you do not find the majority of the questions easy, you should probably take CS 20 before taking CS 121. See also below for the required background.
The following is recommended for all students to go over as a way to prepare for the mathematical contents of CS 121:
Homework Zero ( LaTeX ) - this is one good tool for self assessment. It will be due in the first week of classes but I highly recommend you do it over the summer.
Mathematical background chapter: Regardless of whether you took CS 20 or other proof-based courses, you should read the Mathematical background chapter of the CS121 textbook (pdf version , see also html version) of the CS 121 text before the term begins.
You might find the following student feedback on required background (fall 2017 fall 2018) useful but keep in mind that each person is different and so “your mileage 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 these topics. Some particularly recommended sources are:
Lehman-Leighton-Meyer’s Mathematics for Computer Science notes. These are the notes for MIT 6.042 for which lecture videos are also available online. See below.
Lecture notes for Berkeley CS 70: Discrete Mathematics and Probability Theory
Handouts for Stanford CS 103: Mathematical Foundations for Computing
Margaret Fleck’s building blocks for theoretical computer science
Jim Aspnes’ online available book Notes on Discrete Mathematics
Rosen’s discrete mathematics book (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 proof-based courses, 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 and in particular a nice proof writing checklist. When trying to come up with your own proofs, you might find their 10 techniques to get unstuck useful too.
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. 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 on graphs and pages 431-438 from LLM on directed acyclic graphs (for more depth, you can read all of Chapters 10-12 in LLM), watch Lecture 6, and do Homework 4 as well questions 10.15, 10.18 and 10.22 from LLM.
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. The textbook for STAT 110 is also available on this website.
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. 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.