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&2 | August 28 and 30 | Propositional logic and quantifiers |
Notes [ps]
[pdf]. Background reading on sets [ps] [pdf]. |
3 | September 1 | Proof techniques |
Notes [ps]
[pdf]. |
4&5 | September 6&8 | Induction |
Notes [ps]
[pdf]. [Rosen 3.3] |
6&7 | September 11 & 13 | Stable marriage |
Notes [ps]
[pdf]. |
8&9&10 | September 15, 18 and 20 | Modular Arithmetic and Euclid's Algorithm |
Notes [ps]
[pdf]. [Rosen 2.4 background on division; Rosen pp. 161-165, 177-179] |
11 & 12 | September 22 & 25 | Polynomials, finite fields and Secret Sharing |
Notes [ps]
[pdf]. |
13 &14 | September 29 & October 2 | Error correcting codes, Berlekamp-Welsh decoder |
Notes [ps]
[pdf]. Scribe Lecture notes [ps] [pdf]. |
15 | October 4 | Midterm 1 | |
16&17 | October 6&9 | Eulerian Graphs |
Notes [ps]
[pdf].
[Rosen 2.6]
|
18 & 19 | October 11& 13 | Hypercubes - expansion, gray codes | Notes [ps] [pdf]. |
20 & 21 | October 16 & 18 | Basics of counting |
Notes
[ps]
[pdf]. [Rosen 4.1-4.4] |
22 | October 20 | Basic probability |
Notes [ps]
[pdf]. [Rosen 5.1, 5.2] |
23 & 24 | October 23 & 25 | Conditional probability |
Notes [ps]
[pdf]. [Rosen 5.1, 5.2] |
25 | October 27 | Random variables, expected values |
Notes [ps]
[pdf]. [Rosen 5.3] |
26 & 27 | October 30 & November 1 | Linearity of expectation, variance |
Notes [ps]
[pdf]. [Rosen 5.3] |
28 | November 3 | Midterm 2 | |
29 & 30 | November 6 & 8 | I.I.D. Random Variables |
Notes [ps]
[pdf]. |
31 | November 13 | Estimation, Statistics and Normal Distribution | Continuing with notes from last time. |
32 | November 15 | Two Killer Applications |
Notes [ps]
[pdf]. |
33 | November 17 | Some Important Distributions |
Notes [ps]
[pdf]. |
34 | November 20 | Power Law Distributions |
Lecture Notes [pg1.pdf]
.
[pg2.pdf]
.
[pg3.pdf]
.
[pg4.pdf]
. More Notes Power Laws & Polya Urns. External link: Zipf, Power-laws, and Pareto - a ranking tutorial |
35 | November 27 | How to Lie with Statistics |
Notes [ps]
[pdf]. |
36, 37, 38 & 39 | November 29 & December 1, 4 & 6 | Infinity and diagonalization |
Notes [ps].
[pdf]. |
40 | December 8 | Halting problem |
Notes [ps].
[pdf]. Notes on diagonalization in pdf. Optional: A relevant essay [ps] [pdf] |