CS 70 at UC Berkeley
Discrete Mathematics and Probability Theory
Lecture: M/Tu/W/Th 2-3:30 PM, VLSB 2050
Week 0 Overview
Before CS70
Week 1 Overview
Propositional Logic, Proofs, Induction
- Note -1 : Intro to CS70
- Note 0 : Review of Sets, Notation
- Note 1 : Propositional Logic
- Note 2 : Proofs
- Note 3 : Induction
- Note 5 : Graph Theory
- Note b1 : Bonus Note 1
- Discussion 01a (solution)
- Discussion 01b (solution)
- Discussion 01c (solution)
- Discussion 01d (solution)
- Homework 00 (TeX) (solution)
- Homework 01 (TeX) (solution)
- Lecture 1 (full) (6up)
- Lecture 2 (full) (6up)
- Lecture 3 (full) (6up)
- Lecture 4 (full) (6up)
- Lecture bonus1 (full) (6up)
Week 2 Overview
Graph Theory, Modular Arithmetic
- Note 5 : Graph Theory
- Note 5.5 : Graphs II
- Note 6 : Modular Arithmetic
- Note 6.5 : Chinese Remainder Theorem, Fermat's Little Theorem
- Note b2 : Bonus Note 2
- Discussion 02a (solution)
- Discussion 02b (solution)
- Discussion 02c (solution)
- Homework 02 (TeX) (solution)
- Lecture 5 (full) (6up)
- Lecture 6 (full) (6up)
- Lecture 7 (full) (6up)
- Lecture bonus2 (full) (6up)
Week 3 Overview
RSA, Polynomials, Error-Correcting Codes, Countability
- Note 7 : Public Key Cryptography
- Note 8 : Polynomials
- Note 9 : Error Correcting Codes
- Note 10 : Infinity and Uncountability
- Note b3 : Bonus Note 3
- Discussion 03a (solution)
- Discussion 03b (solution)
- Discussion 03c (solution)
- Discussion 03d (solution)
- Homework 03 (TeX) (solution)
- Lecture 8 (full) (6up)
- Lecture 9 (full) (6up)
- Lecture 10 (full) (6up)
- Lecture 11 (full) (6up)
- Lecture bonus3 (full) (6up)
Week 4 Overview
Midterm 1, Computability, Counting, Introduction to Probability
- Note 11 : Self-Reference and Uncomputability
- Note 12 : Counting
- Note 12.5 : Counting II
- Note 13 : Introduction to Discrete Probability
- Discussion 04a (solution)
- Discussion 04b (solution)
- Discussion 04c (solution)
- Discussion 04d (solution)
- Homework 04 (TeX) (solution)
- Lecture 12 (full) (6up)
- Lecture 13 (full) (6up)
- Lecture 14 (full) (6up)
- Lecture 15 (full) (6up)
- Lecture bonus4 (full) (6up)
Week 5 Overview
Conditional Probability, Random Variables, Discrete R.V. Distributions
- Note 14 : Conditional Probability
- Note 15 : Discrete Random Variables: Intro and Distribution
- Note 15.5 : Random Variables: Expectation
- Note 17 : Hashing and Load Balancing
- Note 19 : Geometric and Poisson Distributions
- Discussion 05a (solution)
- Discussion 05b (solution)
- Discussion 05c (solution)
- Discussion 05d (solution)
- Homework 05 (TeX) (solution)
- Lecture 16 (full) (6up)
- Lecture 17 (full) (6up)
- Lecture 18 (full) (6up)
- Lecture 19 (full) (6up)
Week 6 Overview
Midterm 2, Variance and Covariance, Confidence Intervals
- Note 16 : Random Variables: Variance
- Note 16.5 : Random Variables: Covariance
- Note 18 : Concentration Inequalities and LLN
- Note 19 : Geometric and Poisson Distributions
- Note 20 : Continuous Probability Distributions
- Discussion 06a (solution)
- Discussion 06b (solution)
- Discussion 06c (solution)
- Discussion 06d (solution)
- Homework 06 (TeX) (solution)
- Lecture 20 (full) (6up)
- Lecture 21 (full) (6up)
- Lecture 22 (full) (6up)
- Lecture 23 (full) (6up)
- Lecture bonus6 (full) (6up)
Week 7 Overview
Continuous Probability, Markov Chains
- Note 20 : Continuous Probability Distributions
- Note 21 : Finite Markov Chains
- Discussion 07a (solution)
- Discussion 07b (solution)
- Discussion 07c (solution)
- Discussion 07d (solution)
- Homework 07 (TeX) (solution)
- Lecture 24 (full) (6up)
- Lecture 25 (full) (6up)
- Lecture 26 (full) (6up)
- Lecture 27 (full) (6up)
- Lecture bonus7 (full) (6up)
Week 8 Overview
Final Review, Stable Marriage, Final
- Note 4 : Stable Marriage
- Lecture 28 (full) (6up)
- Lecture 29 (full) (6up)
- Lecture 30 (full) (6up)
- Lecture 31 (full) (6up)
Notes
There is no textbook for this class. Instead, there is a set of comprehensive lecture notes. Make sure you revisit the notes after every lecture, and multiple times thereafter: you should be aware that it will likely take several readings before you fully understand the material. Each note may be covered in one or more lectures. See Policies for more information.
- Note -1: Intro to CS70
- Note 0: Review of Sets, Notation
- Note 1: Propositional Logic
- Note 2: Proofs
- Note 3: Induction
- Note 4: Stable Marriage
- Note 5: Graph Theory
- Note 5.5: Graphs II
- Note 6: Modular Arithmetic
- Note 6.5: Chinese Remainder Theorem, Fermat's Little Theorem
- Note 7: Public Key Cryptography
- Note 8: Polynomials
- Note 9: Error Correcting Codes
- Note 10: Infinity and Uncountability
- Note 11: Self-Reference and Uncomputability
- Note 12: Counting
- Note 12.5: Counting II
- Note 13: Introduction to Discrete Probability
- Note 14: Conditional Probability
- Note 15: Discrete Random Variables: Intro and Distribution
- Note 15.5: Random Variables: Expectation
- Note 16: Random Variables: Variance
- Note 16.5: Random Variables: Covariance
- Note 17: Hashing and Load Balancing
- Note 18: Concentration Inequalities and LLN
- Note 19: Geometric and Poisson Distributions
- Note 20: Continuous Probability Distributions
- Note 21: Finite Markov Chains
- Note b1: Bonus Note 1
- Note b2: Bonus Note 2
- Note b3: Bonus Note 3
Expand
Discussions
The discussion sections will not cover new material, but rather will give you additional practice solving problems. You can attend any discussion section you like. However, if there are fewer desks than students, then students will be admitted to the section on a first-come first-served basis and others will have to attend an alternative section. See Policies for more information.
- Discussion 01a: Propositional Logic (solution)
- Discussion 01b: Proofs (solution)
- Discussion 01c: Induction (solution)
- Discussion 01d: Graphs (solution)
- Discussion 02a: Graphs (solution)
- Discussion 02b: Modular Arithmetic (solution)
- Discussion 02c: Modular Arithmetic, Bijections (solution)
- Discussion 03a: RSA (solution)
- Discussion 03b: Polynomials (solution)
- Discussion 03c: Error Correcting Codes (solution)
- Discussion 03d: Countability (solution)
- Discussion 04a: Computability (solution)
- Discussion 04b: Counting I (solution)
- Discussion 04c: Counting II (solution)
- Discussion 04d: Introduction to Probability (solution)
- Discussion 05a: Conditional Probability (solution)
- Discussion 05b: Independence, Inclusion Exclusion (solution)
- Discussion 05c: Random Variables I (solution)
- Discussion 05d: Random Variables: II (solution)
- Discussion 06a: More Expectation (solution)
- Discussion 06b: Variance (solution)
- Discussion 06c: Covariance (solution)
- Discussion 06d: Inequalities (solution)
- Discussion 07a: Continuous Probability I (solution)
- Discussion 07b: Continuous Probability II (solution)
- Discussion 07c: Markov Chains I (solution)
- Discussion 07d: Markov Chains II (solution)
Expand
Homeworks
Homeworks are graded based on reasonable effort and not accuracy and it is highly recommended that you do them. What this means is that we will give you feedback and a numerical score so you know how you are doing in the class, but this score is not your grade. Instead, as long as you get some credit on a part, it will be counted as if you got full credit. Homework 0 is required for everyone but it will not count towards your grade. Your lowest homework score will be dropped, but this drop should be reserved for emergencies . No additional allowances will be made for late or missed homeworks: please do not contact us about missed homeworks or late submissions. See Policies for more information.
- HW 00: Course Logistics (TeX) (Sol)
- HW 01: Propositional Logic, Proofs, Induction (TeX) (Sol)
- HW 02: Graphs, Modular Arithmetic (TeX) (Sol)
- HW 03: RSA, Polynomials, Countability (TeX) (Sol)
- HW 04: Computability, Counting, Intro to Probability (TeX) (Sol)
- HW 05: Conditional Probability, Random Variables, Discrete Distributions (TeX) (Sol)
- HW 06: Variance, Covariance, Confidence Intervals (TeX) (Sol)
- HW 07: Continuous Probability, Markov Chains (TeX) (Sol)
Expand
Lecture Schedule
- Lecture 1 (6/24): Introduction, Propositional Logic, Truth Tables (full) (6up) (Note -1Note 0Note 1)
- Lecture 2 (6/25): Proofs and Proof Methods (full) (6up) (Note 2)
- Lecture 3 (6/26): Induction (full) (6up) (Note 3)
- Lecture 4 (6/27): Graphs I (full) (6up) (Note 5)
- Lecture bonus1 (6/28): Extra Topics: Formal Proof Systems (full) (6up) (Note b1)
- Lecture 5 (7/01): Graphs II (full) (6up) (Note 5.5)
- Lecture 6 (7/02): Modular Arithmetic (full) (6up) (Note 6)
- Lecture 7 (7/03): Modular Arithmetic(FLT, CLT), Bijections (full) (6up) (Note 6Note 6.5)
- Lecture bonus2 (7/05): Extra Topics: Euler's Totient Function (full) (6up) (Note b2)
- Lecture 8 (7/08): RSA/Cryptography (full) (6up) (Note 7)
- Lecture 9 (7/09): Polynomials (full) (6up) (Note 8)
- Lecture 10 (7/10): Error Correcting Codes (full) (6up) (Note 9)
- Lecture 11 (7/11): Countability (full) (6up) (Note 10)
- Lecture bonus3 (7/12): Cantor-Schroder-Bernstein (full) (6up) (Note b3)
- Lecture 12 (7/15): Computability (full) (6up) (Note 11)
- Lecture 13 (7/16): Counting, Combinatorial Proofs I (full) (6up) (Note 12)
- Lecture 14 (7/17): Counting, Combinatorial Proofs II (full) (6up) (Note 12.5)
- Lecture 15 (7/18): Probability Space, Complements, Symmetry, Birthday / Monty Hall (full) (6up) (Note 13)
- Lecture bonus4 (7/19): The Catalan Numbers (full) (6up) ()
- Lecture 16 (7/22): Conditional Probability, Total Probability Theorem, Bayes Rule (full) (6up) (Note 14)
- Lecture 17 (7/23): Independence, Unions, Intersections, Inclusion-Exclusion (full) (6up) (Note 13Note 14)
- Lecture 18 (7/24): Random Variables, Bernoulli, Binomial, Geometric, Poisson (full) (6up) (Note 15)
- Lecture 19 (7/25): Joint PMF, Independence, Expectation of Random Variables, Linearity (full) (6up) (Note 15.5)
- Lecture Extra (7/26): Hashing and Load Balancing (Guest Lecture) (Note 17)
- Lecture 20 (7/29): Expectation Continued: Tail Sum Bound, Geometric, Poisson, Coupon Collector (full) (6up) (Note 15.5Note 19)
- Lecture 21 (7/30): Variance (full) (6up) (Note 16Note 19)
- Lecture 22 (7/31): Independent RVs, Covariance, Correlation (full) (6up) (Note 16.5Note 19)
- Lecture 23 (8/01): Markov, Chebyshev, Law of Large Numbers (full) (6up) (Note 18)
- Lecture bonus6 (8/02): MT2 Review (full) (6up) ()
- Lecture 24 (8/05): Continuous RV, PDF, CDF, Joint CDF, Uniform, Exponential (full) (6up) (Note 20)
- Lecture 25 (8/06): Conditional PDF, Normal RVs, Central Limit Theorem (full) (6up) (Note 20)
- Lecture 26 (8/07): Markov Chain Definition, n-Step Transition Probabilities, Hitting Times (full) (6up) (Note 21)
- Lecture 27 (8/08): Classification Of States, Law of Large Numbers for Markov Chains, Markov Chain Convergence Theorem (full) (6up) (Note 21)
- Lecture bonus7 (8/09): Markov Chain Mixing Times (full) (6up) ()
- Lecture 28 (8/12): Final Review (Discrete Math) (full) (6up) ()
- Lecture 29 (8/13): Final Review (Probability Theory) (full) (6up) ()
- Lecture 30 (8/14): Extra Topics: Poisson Processes (full) (6up) ()
- Lecture 31 (8/15): Extra Topics: Stable Marriage (full) (6up) (Note 4)