Welcome to CS 70!
Section: Tu/Th 5-6pm in Soda 405
Office Hours: Mon/Wed 5-6pm in Cory 400*
*office hours will be held remotely at oh.eecs70.org on 8/30 and 9/1
| Discussion Date | Topics | Extra Materials |
| 8/31 (1a) | Propositional logic Inverse, converse, and contrapositive Proving set equivalence Functions: Image, Pre-image Pigeonhole principle | How to succeed in CS 70 (one TA’s opinion) Problem 3b notes |
| 9/2 (1b) | General proof practice Primes, divisibility, remainders Induction Advanced induction strategy: Prove a stronger statement | Very short induction summary |
| 9/7 (2a) | Stable matching: Propose-and-reject algorithm, Optimal / Pessimal stable matchings | Discussion 2a notes |
| 9/9 (2b) | Graphs: Eulerian tours and walks, Bipartite graphs / coloring, Induction on graphs | Discussion 2b notes |
| 9/14 (3a) | Graphs: Planarity (Euclid’s formula, K5 and K33) Trees, forests, and connected components Hypercubes | Discussion 3a notes |
| 9/16 (3b) | Modular Arithmetic: Definition, mod rules, tricks for simplifying formulas Inverses and GCD Euclid’s GCD algorithm | Discussion 3b notes |
| 9/21 (4a) | Extended Euclidean algorithm Fermat’s Little Theorem (FLT) Functions and bijections Review on your own: CRT | Just for fun: How Ancient War Trickery Is Alive in Math Today (CRT article from Quanta Magazine) Discussion 4a notes |
| 9/23 (4b) | RSA: Public and private keys Encryption and decryption Hardness of factoring Applications of CRT | Discussion 4b notes |
| 9/28 (5a) | Polynomials: Roots and degrees Lagrange Interpolation Secret sharing | Discussion 5a notes |
| 9/30 (5b) | Error Correcting: Erasure errors and general errors Berlekamp-Welch algorithm Secret sharing with errors | Discussion 5b notes |
| 10/5 (6a) | Counting: Binomial coefficients Stars and Bars Rules of counting | Discussion 6a notes |
| 10/7 (6b) | Counting Combinatorial proofs Extremely brief introduction to countability | Discussion 6b notes Out of scope but interesting article on the Continuum Hypothesis (read the notes on countability first!) |
| 10/12 (7a) | Countability and Computability | Notes on injections, surjections, and bijections |
| 10/14 (no worksheet) | Midterm review | Graph terms cheat sheet Bonus notes on counting, polynomials, modular arithmetic, and graphs All courtesy of TA Brianna Fan! |
| 10/19 (8a) | Discrete probability: Sample spaces, events, unions and intersections | Discussion 8a notes Survey (anonymous & short!) |
| 10/21 (8b) | Discrete probability: Conditional probability, Bayes’ rule, Independence, Simpson’s Paradox | Discussion 8b notes |
| 10/26 (9a) | Discrete probability review: Conditional probability, independence, disjoint events, total probability rule | Discussion 9a notes |
| 10/28 (9b) | Random variables: Union bound, binomial and geometric distributions | Discussion 9b notes |
| 11/2 (10a) | Expected value, linearity of expectation, indicator variables | Discussion 10a notes |
| 11/4 (10b) | Expected value, indicator variables, memoryless property of geometric distributions | Discussion 10b notes |
| 11/9 (11a) | Variance Geometric distribution and coupon collector Poisson distributions | Discussion 11a notes |
| 11/16 (12a) | Conditional expectation Joint distributions and a common mistake to avoid: E(XY) is not necessarily equal to E(X)E(Y)! Markov’s Inequality Chebyshev’s Inequality | Discussion 12a notes |
| 11/18 (12b) | The strike has been cancelled. I will be holding discussion at the usual time. I will keep the walkthrough posted here anyway. | Discussion 12b walkthrough |
| Thanksgiving week | Discussions will not be meeting this week. See Piazza post for logistical details. | |
| 11/30 (14a) | Continuous probability: Expected values and variance (now with integrals!), normal distribution and sum of normals, central limit theorem (CLT) | Discussion 14a notes |
| 12/2 (14b) Last Official Section! | Covariance and correlation (biliniarity!) Linear least squares estimator Joint and marginal distributions | Discussion 14b notes |
| 12/9 (Unofficial review session) | Review Session: 5pm on 12/9, in the usual classroom. |
See you in class!
