CS 70, Fall 2021

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 DateTopicsExtra 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
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
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 ComputabilityNotes on injections, surjections, and bijections
10/14 (no worksheet)Midterm reviewGraph 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 variablesDiscussion 10a notes
11/4 (10b)Expected value, indicator variables, memoryless property of geometric distributionsDiscussion 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 weekDiscussions 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!