CS 70 at UC Berkeley
Discrete Mathematics and Probability Theory
Lectures: Tu/Th 12:30-2 pm, Wheeler 150
Professor Alistair Sinclair
sinclair (at) berkeley (dot) edu
Office Hours: M 1-2 pm, Tu 2:15-3:15 pm, 677 Soda
Professor Yun S. Song
yss (at) berkeley (dot) edu
Office Hours: M 11 am - 12 pm, 629 Soda; Tu 5-6 pm, 304B Stanley Hall
Week 0 Overview
Propositional Logic
Week 1 Overview
Proofs, Induction
Week 2 Overview
Stable Marriage, Graphs
Week 3 Overview
Graphs, Modular Arithmetic
Week 4 Overview
RSA, Polynomials
Week 5 Overview
Midterm, Polynomials
Week 6 Overview
Countability, Computability
Week 7 Overview
Counting, Introduction to Probability
Week 8 Overview
Conditional Probability, Independence
Week 9 Overview
Random Variables, Joint Distributions, Linearity of Expectation, Variance
Week 10 Overview
Applications, Midterm
Week 11 Overview
Inequalities, Geometric, Poisson
Week 12 Overview
Continuous Random Variables
Week 13 Overview
Continuous Random Variables, Markov Chains
Week 14 Overview
Continuous Random Variables, Markov Chains
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 0: Review of Sets, Notation
- Note 1: Propositional Logic
- Note 2: Proofs
- Note 3: Induction
- Note 4: Stable Marriage
- Note 5: Graph Theory
- Note 6: Modular Arithmetic
- 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 13: Introduction to Discrete Probability
- Note 14: Conditional Probability
- Note 15: Random Variables: Distribution & Expectation
- Note 16: Random Variables: Variance & Covariance
- Note 17: Applications
- Note 18: Concentration Inequalities and LLN
- Note 19: Geometric and Poisson Distributions
- Note 20: Continuous Probability Distributions
- Note 21: Finite Markov Chains
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 00b: Propositional Logic (solution)
- Discussion 01a: Proofs (solution)
- Discussion 01b: Induction (solution)
- Discussion 02a: Stable Marriage (solution)
- Discussion 02b: Graphs I (solution)
- Discussion 03a: Graphs II (solution)
- Discussion 03b: Modular Arithmetic I (solution)
- Discussion 04a: Modular Arithmetic II (solution)
- Discussion 04b: RSA (solution)
- Discussion 05b: Polynomials, Secret Sharing, Error-Correcting Codes (solution)
- Discussion 06a: Error-Correcting Codes, Countability (solution)
- Discussion 06b: Countability, Computability (solution)
- Discussion 07a: Counting, Combinatorial Proofs (solution)
- Discussion 07b: Introduction to Discrete Probability (solution)
- Discussion 08a: Conditional Probability, Bayes' Rule, Total Probability Rule (solution)
- Discussion 08b: Independence, Combination of Events, Inclusion-Exclusion, Union Bound (solution)
- Discussion 09a: Random Variables and Expectaion (solution)
- Discussion 09b: Variance (solution)
- Discussion 10a: Applications (solution)
- Discussion 11a: Inequalities (solution)
- Discussion 11b: Geometric and Poisson Distributions (solution)
- Discussion 12a: Continuous I (solution)
- Discussion 12b: Continuous II (solution)
- Discussion 14a: Continuous III, Markov Chains (solution)
- Discussion 14b: Markov Chains (solution)
Homeworks
Homeworks are graded for accuracy and it is highly recommended that you do them. Your lowest two homework scores will be dropped, but these drops 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 (TeX) (Sol)
- HW 02: Induction, Stable Marriage (TeX) (Sol)
- HW 03: Graphs (TeX) (Sol)
- HW 04: Modular Arithmetic (TeX) (Sol)
- HW 05: RSA (TeX) (Sol)
- HW 06: Polynomials, Error Correcting Codes (TeX) (Sol)
- HW 07: Countability, Computability, Counting (TeX) (Sol)
- HW 08: Counting, Introducion to Probability (TeX) (Sol)
- HW 09: Independence, Random Variables (TeX) (Sol)
- HW 10: Variance, Joint Distributions (TeX) (Sol)
- HW 11: Applications, Inequalities (TeX) (Sol)
- HW 12: Geometric and Poisson Distributions, Continuous Random Variables (TeX) (Sol)
- HW 13: Continuous Random Variables, Markov Chains (TeX) (Sol)
Lecture Schedule
- Lec 1 (8/23): Intro & Propositional Logic (Note 1)
- Lec 2 (8/28): Proofs (Note 2)
- Lec 3 (8/30): Induction (Note 3)
- Lec 4 (9/4): Stable Marriage (Note 4)
- Lec 5 (9/6): Graph Theory I (Note 5)
- Lec 6 (9/11): Graph Theory II (Note 5)
- Lec 7 (9/13): Modular Arithmetic (Note 6)
- Lec 8 (9/18): RSA (Note 7)
- Lec 9 (9/20): Polynomials (Note 8)
- Lec 10 (9/27): Error-Correcting Codes (Note 9)
- Lec 11 (10/2): Infinity Countability (Note 10)
- Lec 12 (10/4): Self-Ref and Uncomputability (Note 11)
- Lec 13 (10/9): Counting (Note 12)
- Lec 14 (10/4): Introduction to Probability (Note 13)
- Lec 15 (10/16): Conditional Probability (Note 14)
- Lec 16 (10/18): Combinations of Events (Note 14)
- Lec 17 (10/23): Random Variables I (Note 15)
- Lec 18 (10/25): Random Variables II (Note 16)
- Lec 19 (10/30): Applications (Note 17)
- Lec 20 (11/6): Concentration Inequality, LLN (Note 18)
- Lec 21 (11/8): Geometric and Poisson Dist'n (Note 19)
- Lec 22 (11/13): Continuous Distributions I (Note 20)
- Lec 23 (11/15): Continuous Distributions II (Note 20)
- Lec 24 (11/27): Markov Chains I (Note 21)
- Lec 25 (11/29): Markov Chains II (Note 21)