CS 70 at UC Berkeley
Discrete Mathematics and Probability Theory
Lecture: TuTh 3:30-5:00pm, Wheeler 150
Professor Alistair Sinclair
sinclair (at) berkeley (dot) edu
Office Hours: M 1:15-2:15PM, W 1:15-2:15PM, 677 Soda Hall
Professor Yun S. Song
yss (at) berkeley (dot) edu
Office Hours: W 11am-12pm, 629 Soda Hall; Th 5:15-6:15pm, 304B Stanley Hall
Week 0 Overview
Welcome to CS70!
Week 1 Overview
Propositional Logic, Proofs, Induction
Week 2 Overview
Stable Marriage, Graph Theory
Week 3 Overview
Graph Theory, Modular Arithmetic
Week 4 Overview
Public Key Cryptography, Polynomials
Week 5 Overview
Error Correcting Codes, Countability
Week 6 Overview
Midterm 1, Counting
- Discussion 6b (solution)
- Homework 5 (TeX) (solution)
- Homework 6 (TeX) (solution)
Week 7 Overview
Counting
Week 8 Overview
Introduction to Probability, Conditional Probability
Week 9 Overview
Conditional Probability, Random Variables I
Week 10 Overview
Random Variables II, Concentration Inequalities, Law of Large Numbers
Week 11 Overview
Midterm 2, Hashing and Load Balancing
Week 12 Overview
Geometric and Poisson, Continuous Probability Distributions
Week 13 Overview
Continuous Probability Distributions, Thanksgiving Break
Week 14 Overview
Markov Chains, Decidability
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: Counting
- Note 12: Introduction to Discrete Probability
- Note 13: Conditional Probability
- Note 14: Random Variables: Distribution & Expectation
- Note 15: Random Variables: Variance & Covariance
- Note 16: Concentration Inequalities and LLN
- Note 17: Applications: Hashing and Load Balancing
- Note 18: Geometric and Poisson Distributions
- Note 19: Continuous Probability Distributions
- Note 20: Finite Markov Chains
- Note 21: Self-Reference and Uncomputability
Discussions
The discussion sections are specifically designed to consolidate the material covered in lectures and in the notes. It is highly recommended that you attend both discussions each week. You may attend any discussion section, but we recommend that you settle on a weekly two-section pair (with the same TA) as early as possible in the semester. If a particular section is too full, then students will be admitted on a first-come first-served basis and others will have to attend an alternative section. All sections are equivalent: they all cover the same material. See Policies for more information.
- Discussion 1: Propositional Logic, Proofs (solution)
- Discussion 1b: Quiz (Logic, Proofs) (solution)
- Discussion 2: Induction, Stable Marriage (solution)
- Discussion 2b: Quiz (Induction, Stable Marriage) (solution)
- Discussion 3: Graph Theory (solution)
- Discussion 3b: Quiz (Graph Theory) (solution)
- Discussion 4: Modular Arithmetic and RSA (solution)
- Discussion 4b: Quiz (Modular Arithmetic and RSA) (solution)
- Discussion 5: Polynomials and Error-Correcting Codes (solution)
- Discussion 6: Countability (solution)
- Discussion 6b: Quiz (Countability) (solution)
- Discussion 7: Counting (solution)
- Discussion 7b: Quiz (Counting) (solution)
- Discussion 8: Counting and Probability (solution)
- Discussion 8b: Quiz (Counting and Probability) (solution)
- Discussion 9: Conditional Probability and Combinations of Events (solution)
- Discussion 9b: Quiz (Conditional Probability and Combinations of Events) (solution)
- Discussion 10: Random Variables (solution)
- Discussion 11: Concentration Inequalities, LLN and Applications (solution)
- Discussion 11b: Quiz (Concentration Inequalities, LLN and Applications) (solution)
- Discussion 12: Geometric and Poisson Distributions (solution)
- Discussion 12b: Quiz (Geometric and Poisson Distributions) (solution)
- Discussion 13: Continuous Distributions (solution)
- Discussion 14: Markov Chains (solution)
Homeworks
There will be weekly required homeworks, again designed to consolidate your understanding of the course material. It is highly recommended that you attempt all homeworks. 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 1: Propositional Logic, Proofs (TeX) (Sol)
- HW 2: Induction, Stable Marriage (TeX) (Sol)
- HW 3: Graph Theory (TeX) (Sol)
- HW 4: Modular Arithmetic and RSA (TeX) (Sol)
- HW 5: Polynomials and Error-Correcting Codes (TeX) (Sol)
- HW 6: Countability (TeX) (Sol)
- HW 7: Counting (TeX) (Sol)
- HW 8: Counting and Probability (TeX) (Sol)
- HW 9: Conditional Probability and Combinations of Events (TeX) (Sol)
- HW 10: Random Variables (TeX) (Sol)
- HW 11: Concentration Inequalities, LLN and Applications (TeX) (Sol)
- HW 12: Geometric and Poisson Distributions (TeX) (Sol)
- HW 13: Continuous Distributions and Markov Chains (TeX) (Sol)
Lecture Schedule
- Lecture 1 (8/29): Introduction & Logic (Note 1)
- Lecture 2 (9/3): Proofs (Note 2)
- Lecture 3 (9/5): Induction (Note 3)
- Lecture 4 (9/10): Stable Marriage (Note 4)
- Lecture 5 (9/12): Graphs I (Note 5)
- Lecture 6 (9/17): Graphs II (Note 5)
- Lecture 7 (9/19): Modular Arithmetic (Note 6)
- Lecture 8 (9/24): Public Key Cryptography: RSA (Note 7)
- Lecture 9 (9/26): Polynomials (Note 8)
- Lecture 10 (10/1): Error-Correcting Codes (Note 9)
- Lecture 11 (10/3): Countability (Note 10)
- Lecture 12 (10/15): Counting I (Note 11)
- Lecture 13 (10/17): Counting II (Note 11)
- Lecture 14 (10/22): Introduction to Probability (Note 12)
- Lecture 15 (10/24): Conditional Probability (Note 13)
- Lecture 16 (10/24): Combinations of Events (Note 13)
- Lecture 17 (10/29): Random Variables I (Note 14)
- Lecture 18 (11/5): Random Variables II (Note 15)
- Lecture 19 (11/7): Concentration Inequalities and LLN (Note 16)
- Lecture 20 (11/14): Applications (Note 17)
- Lecture 21 (11/19): Geometric and Poisson Distributions (Note 18)
- Lecture 22 (11/21): Continuous Distributions I (Note 19)
- Lecture 23 (11/26): Continuous Distributions II (Note 19)
- Lecture 24 (12/3): Finite Markov Chains (Note 20)
- Lecture 25 (12/5): Self-Reference and Uncomputability (Note 21)