cs70 is required for L&S CS majors; EECS majors have a choice of cs70 or Math55. Broadly speaking the two courses cover similar material; however, Math55 covers a wider range of topics in less depth and with fewer applications, and is less closely tailored to Computer Science. You should take this course as an alternative to Math55 if you are intending to major in Computer Science and if you found the more conceptual parts of CS61A enjoyable and relatively straightforward.
The following schedule is tentative and subject to change. Readings in Rosen are optional, in case you want extra background on the subject or a different presentation from a second point of view.
Topic | Readings | ||
1 | Jan 17 | Propositional logic and quantifiers |
Notes [ps]
[pdf]. |
2 | Jan 19 | Proof techniques |
Notes [ps]
[pdf]. |
3 | Jan 24 | Induction |
Notes [ps]
[pdf]. [Rosen 3.3] |
4 | Jan 26 | Strong induction and well-ordering principle |
Notes [ps]
[pdf]. [Rosen 3.3] |
5&6 | Jan 31 & Feb 2 | Stable marriages | External notes |
7&8&9 | Feb 7 & Feb 9 and Feb 14 | Modular Arithmetic and Euclid's Algorithm |
Notes [ps]
[pdf]. [Rosen 2.4 background on division; Rosen pp. 161-165, 177-179] |
10 | Feb 16 | Chinese Remainder Theorem & Fingerprinting |
Notes [ps]
[pdf]. [Rosen pp. 185-187] |
11 | Feb 21 | Polynomials, finite fields and Secret Sharing |
Notes [ps]
[pdf]. |
12 | Feb 23 | Secret sharing contd. |
(continuing from same notes as last time). |
13 | Feb 28 | Error correcting codes, Berlekamp-Welsh decoder |
Notes [ps]
[pdf]. Scribe Lecture notes [ps] [pdf]. |
14 | Mar 2 | Midterm 1 | |
15&16 | Mar 7&9 | Eulerian Graphs |
Notes [ps]
[pdf].
[Rosen 2.6]
Optional reading on Hypercubes [ps] [pdf]. |
17 | Mar 14 | Basics of counting |
Notes
[ps]
[pdf]. [Rosen 4.1-4.4] |
18 | Mar 16 | Basic probability |
Notes [ps]
[pdf]. [Rosen 5.1, 5.2] |
19 & 20 | Mar 21 & 23 | Conditional probability |
Notes [ps]
[pdf]. [Rosen 5.1, 5.2] |
Mar 28 | No class! Enjoy Spring break. | ||
Mar 30 | No class! Enjoy Spring break. | 21 | Apr 4 | Midterm Review |
Study Guide and Practice Problems [ps]
[pdf]. Selected Solutions [ps] [pdf]. |
Apr 6 | Midterm 2 | ||
22 | Apr 11 | Random variables, expected values |
Notes [ps]
[pdf]. [Rosen 5.3] |
23 | Apr 13 | Linearity of expectation, variance |
Notes [ps]
[pdf]. [Rosen 5.3] |
24 | Apr 18 | Variance, tail bounds | (Continuing from same notes as last time) |
25 | Apr 20 | Some Important Distributions |
Notes [ps]
[pdf]. |
26 & 27 | Apr 25 & 27 | Estimation, Statistics and Normal Distribution |
Notes [ps]
[pdf]. |
28 | May 2 | How to Lie with Statistics |
Notes [ps]
[pdf]. |
29 | May 4 | Countability, diagonalization, computability | Notes [txt]. |
30 | May 9 | Halting problem |
Optional: A relevant essay
[ps] [pdf] |