CS 70 at UC Berkeley
Discrete Mathematics and Probability Theory
Lectures: M/Tu/W/Th 2-3:30 pm, 155 Dwinelle
Week 1 Overview
Propositional Logic, Proofs, Induction
- Note 0 : Review of Sets, Notation
- Note 1 : Propositional Logic
- Note 2 : Proofs
- Note 3 : Induction
- Note 3a : Well Ordering Principle
- Note 3b : Common Knowledge
- Discussion 01a
- Discussion 01b
- Discussion 01c
- Discussion 01d
- Homework 00 (TeX)
- Homework 01 (TeX)
- Lecture 1 (full) (6up)
- Lecture 2 (full) (6up)
- Lecture 3 (full) (6up)
- Lecture 4 (full) (6up)
Week 2 Overview
Graph Theory, Modular Arithmetic, RSA
- Note 5 : Graph Theory
- Note 5a : Planar Duality
- Note 6 : Modular Arithmetic
- Note 7 : Bijections and RSA
- Note 7a : Euler's Totient Function
- Note 7b : RSA Extras
- Discussion 02a
- Discussion 02b
- Discussion 02c
- Discussion 02d
- Homework 02 (TeX)
- Lecture 5 (full) (6up)
- Lecture 6 (full) (6up)
- Lecture 7 (full) (6up)
- Lecture 8 (full) (6up)
Week 3 Overview
Polynomials, Error Correcting Codes, Uncountability
- Note 6a : Chinese Remainder Theorem
- Note 8 : Polynomials
- Note 8a : Polynomial Division Theorem
- Note 9 : Error Correcting Codes
- Note 10 : Infinity and Uncountability
- Note 10a : Cantor-Schröder-Bernstein Theorem
- Discussion 03a
- Discussion 03b
- Discussion 03d
- Homework 03 (TeX)
- Lecture 9 (full) (6up)
- Lecture 10 (full) (6up)
- Lecture 11 (full) (6up)
Week 4 Overview
Midterm 1, Computability, Counting, Introduction to Probability
Week 5 Overview
Bayes' Rule, Random Variables
Week 6 Overview
Covariance, Tail Sum, Coupon Collector's Problem
Week 7 Overview
Inequalities, Markov Chains
Week 8 Overview
Review, Applications, Final
Notes
There is no textbook for this class. Instead, there is a set of fairly comprehensive lecture notes. Make sure you revisit the notes after lecture. Each note may be covered in one or more lectures. See Syllabus for more information.
- Note 0: Review of Sets, Notation (PDF)
- Note 1: Propositional Logic (PDF)
- Note 2: Proofs (PDF)
- Note 3: Induction (PDF)
- Note 3a: Well Ordering Principle (PDF)
- Note 3b: Common Knowledge (PDF)
- Note 4: Stable Marriage (PDF)
- Note 5: Graph Theory (PDF)
- Note 5a: Planar Duality (PDF)
- Note 6: Modular Arithmetic (PDF)
- Note 6a: Chinese Remainder Theorem (PDF)
- Note 7: Bijections and RSA (PDF)
- Note 7a: Euler's Totient Function (PDF)
- Note 7b: RSA Extras (PDF)
- Note 8: Polynomials (PDF)
- Note 8a: Polynomial Division Theorem (PDF)
- Note 9: Error Correcting Codes (PDF)
- Note 10: Infinity and Uncountability (PDF)
- Note 10a: Cantor-Schröder-Bernstein Theorem (PDF)
- Note 11: Self-Reference and Uncomputability (PDF)
- Note 12: Counting (PDF)
- Note 13: Introduction to Discrete Probability (PDF)
- Note 14: Conditional Probability (PDF)
- Note 15: Two Killer Applications (PDF)
- Note 16: Random Variables: Distribution and Expectation (PDF)
- Note 17: Variance (PDF)
- Note 18: Chebyshev's Inequality (PDF)
- Note 19: Some Important Distributions (PDF)
- Note 20: Continuous Probability (PDF)
- Note 24: Markov Chains (PDF)
- Note 25a: Review of Probability (PDF)
- Note 25b: Probability: An Overview (PDF)
- Note 26: Estimation (PDF)
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 who are officially enrolled in that section will get seating priority. See Syllabus for more information.
- Discussion 01a: Propositional Logic
- Discussion 01b: Proofs
- Discussion 01c: Induction
- Discussion 01d: Well-Ordering Principle, Intro to Graph Theory
- Discussion 02a: Graphs (Trees, Planar Graphs, Planar Duality, Euler's Formula)
- Discussion 02b: Graphs (Coloring, Hypercubes), Modular Arithmetic I
- Discussion 02c: Modular Aritmetic II (Euclid's Algorithm, Chinese Remainder Theorem)
- Discussion 02d: Modular Arithmetic III (Euler's Totient, FLT), RSA
- Discussion 03a: CRT, Polynomials
- Discussion 03b: Secret Sharing, Error Correcting
- Discussion 03d: Uncountability
- Discussion 04a: Computability
- Discussion 04b: Counting
- Discussion 04c: Probability, the Birthday Paradox
- Discussion 04d: Conditional Probability, Total Probability Theorem
- Discussion 05a: Bayes' Rule, Independence
- Discussion 05b: Random Variables
- Discussion 05c: Expectation, Joint PMFs
- Discussion 05d: Conditional PMFs, Variance, Covariance
- Discussion 06a: Covariance, Tail Sum Formula
- Discussion 06b: Memoryless Property, Conditional Expectation, Coupon Collector's Problem
- Discussion 06c: Continuous Probability
- Discussion 06d: Joint / Conditional PDFs, Normal RV's, CLT
- Discussion 07a: Inequalities, Confidence intervals
- Discussion 07b: Introduction to Markov Chains
- Discussion 07c: Hitting times, Balance equations
- Discussion 07d: Limit Theorems
- Discussion 08a: Inequalities, Confidence intervals
- Discussion 08b: Introduction to Markov Chains
Expand
Homeworks
All homeworks are graded for accuracy and it is highly-recommended that you do them. Your lowest homework score will be dropped, but this drop should be reserved for emergencies. The TeX files we provide are not meant to be compiled. They are just provided as a reference. See Syllabus for more information.
- Homework 00: Course Logistics (TeX)
- Homework 01: Propositional Logic, Proof Techniques (TeX)
- Homework 02: Induction, Well-Ordering Principle, Graph Theory, Introduction to Modular Arithmetic (TeX)
- Homework 03: Bijections, Modular Arithmetic (Inverses, Euclid's Algorithm, Totient, FLT, CRT), RSA, Polynomials, Secret Sharing (TeX)
- Homework 04: Countability, Computability, Counting (TeX)
- Homework 05: Introduction to Probability, Random Variables (TeX)
- Homework 06: Expectation, Variance, Memoryless Property, Coupon Collector's (TeX)
- Homework 07: Inequalities, Confidence Intervals, LLN (TeX)
- Homework 08: Markov Chains (TeX)
Expand
Lecture Slides
The lecture schedule can be found here. We recommend reading the notes in advance.
- Lecture 1: Introduction, Propositional Logic, First-Order Logic (full) (6up)
- Lecture 2: Proofs (full) (6up)
- Lecture 3: Induction (full) (6up)
- Lecture 4: Well Ordering Principle, Induction, Graph Theory (Eulerian Tours) (full) (6up)
- Lecture 5: Graph Theory (Trees, Planarity) (full) (6up)
- Lecture 6: Graph Theory (Planarity, Coloring, Hypercubes), Modular Arithmetic (Multiplicative Inverses) (full) (6up)
- Lecture 7: Bijections, Modular Arithmetic (Multiplicative Inverses, Euclid's Algorithm) (full) (6up)
- Lecture 8: Modular Arithmetic (Euler's Totient Function, Fermat's Little Theorem), One-Time Pad, RSA, Digital Signatures (full) (6up)
- Lecture 9: Modular Arithmetic (Chinese Remainder Theorem), Polynomials (Roots, Lagrange Interpolation) (full) (6up)
- Lecture 10: Secret Sharing, Error Correction (Reed-Solomon Codes, Hamming Distance, Berlekamp-Welch Decoding) (full) (6up)
- Lecture 11: Countability, Diagonalization (full) (6up)
- Lecture 28: Discrete Mathematics Review (full) (6up)
- Lecture 29: Probability Theory Review (full) (6up)
- Lecture 30: Stable Marriage (full) (6up)
- Lecture 31: Load Balancing, Hashing (Universal Hashing, FKS Hashing) (full) (6up)
Expand