Homework zero

Prerequisites and background

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.

Resources for math background

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

Self study using MIT 6.042j

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: