Fall 2016 CS70 at UC Berkeley
Discrete Mathematics and Probability Theory
Lectures: MWF 1:00 - 1:59 p.m., Pauley Ballroom
Professor Sanjit Seshia
sseshia@eecs (dot) berkeley (dot) edu
Office Hours: M/W 2-3 p.m. in Cory 566
Week 0 Overview
Propositional Logic and Proofs
Week 1 Overview
Induction, SMA
Week 2 Overview
Graph Theory
Week 3 Overview
Graph Theory II, Modular Arithmetic
Week 4 Overview
Modular Arithmetic, Bijections, RSA
Week 5 Overview
RSA, Polynomials
Week 6 Overview
Error Correction, Countability, Computability
Week 7 Overview
Counting, Probability Space, Conditional Probability
- Note 11 : Self-Reference and Uncomputability
- Note 12 : Counting
- Note 13 : Introduction to Discrete Probability
- Note 14 : Conditional Probability
- Note 25b : Probability: An Overview
- Discussion 07a (solution)
- Discussion 07b (solution)
- Homework 07 (Tex) (solution)
- Slides 17 (full) (6up)
- Slides 18 (full) (6up)
- Slides 20 (full) (6up)
- Slides 21 (full) (6up)
Week 9 Overview
Coupons, Random Variables, Distributions
Week 10 Overview
Expectation, Variance, Inequalities
Week 11 Overview
Linear, Nonlinear Regression, Conditional Expectation
Week 12 Overview
Continuous Probability, Markov Chains
Week 13 Overview
Continuous Probability
- Discussion 13a (solution)
- Homework 13 (Tex) (solution)
- Slides 35 (full) (6up)
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
- Note 1: Propositional Logic
- Note 2: Proofs
- Note 3: Induction
- Note 4: Stable Marriage
- Note 5: Graph Theory
- Note 6: Modular Arithmetic
- Note 7: Bijections and RSA
- 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: Two Killer Applications
- Note 16: Random Variables: Distribution and Expectation
- Note 17: Variance
- Note 18: Chebyshev's Inequality
- Note 19: Some Important Distributions
- Note 20: Continuous Probability
- Note 24: Markov Chains
- Note 25a: Review of Probability
- Note 25b: Probability: An Overview
- Note 26: Estimation
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: Prop. Logic, Proofs (solution)
- Discussion 01b: Induction (solution)
- Discussion 02a: Induction, SMA (solution)
- Discussion 02b: Strong Induction, SMA (solution)
- Discussion 03a: Graph Theory (solution)
- Discussion 03b: Graph Theory (solution)
- Discussion 04b: Modular Arithmetic (solution)
- Discussion 05a: Bijections, RSA (solution)
- Discussion 05b: Fermat's Little Theorem (solution)
- Discussion 06a: Polynomials (solution)
- Discussion 06b: Error Correction (solution)
- Discussion 07a: Countability, Computability (solution)
- Discussion 07b: Counting (solution)
- Discussion 08a: Basic Probability (solution)
- Discussion 08b: Conditional Probability (solution)
- Discussion 09b: Probability, Independence (solution)
- Discussion 10a: Random Variable, Expectation (solution)
- Discussion 10b: Variance, Inequalities (solution)
- Discussion 11a: LLN, LLSE (solution)
- Discussion 11b: Conditional Expectation (solution)
- Discussion 12a: Markov Chain I (solution)
- Discussion 12b: Markov Chains II (solution)
- Discussion 13a: Continunous Probability I (solution)
- Discussion 14a: Continunous Probability II (solution)
- Discussion 14b: Continunous Probability III (solution)
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. See Syllabus for more information.
- Homework 01: Prop. Logic, Proofs (Tex) (solution)
- Homework 02: Induction, SMA (Tex) (solution)
- Homework 03: SMA, Graph (Tex) (solution)
- Homework 04: Modular Arithmetic (Tex) (solution)
- Homework 05: Modular Arithmetic, RSA (Tex) (solution)
- Homework 06: Polynomial (Tex) (solution)
- Homework 07: Countability (Tex) (solution)
- Homework 08: Counting (Tex) (solution)
- Homework 09: Basic Probability (Tex) (solution)
- Homework 10: Random Variable (Tex) (solution)
- Homework 11: Inequalities etc. (Tex) (solution)
- Homework 12: Conditional Expectation (Tex) (solution)
- Homework 13: Markov Chain, Continuous Probability (Tex) (solution)
- Homework 14: Continuous Probability (Tex) (solution)
Expand
Lecture Slides
Slides generally follow the notes. Lecture videos are provided via CalCentral. See Syllabus for more information.
- Lecture 1 (full) (6up): Propositional Logic
- Lecture 2 (full) (6up): Proofs
- Lecture 3 (full) (6up): Induction
- Lecture 4 (full) (6up): Strong Induction
- Lecture 5 (full) (6up): Stable Marriage Algorithm
- Lecture 6 (full) (6up): Graph Theory
- Lecture 7 (full) (6up): Graph Theory II
- Lecture 8 (full) (6up): Modular Arithmetic
- Lecture 9 (full) (6up): EGCD, Multiplicative Inverses
- Lecture 10 (full) (6up): Midterm 1 Review
- Lecture 11 (full) (6up): Bijections, RSA
- Lecture 12 (full) (6up): Fermat's Little Theorem
- Lecture 13 (full) (6up): Polynomial
- Lecture 14 (full) (6up): Polynomials, Error Correcting
- Lecture 15 (full) (6up): Berlekamp Welch
- Lecture 16 (full) (6up): Uncountability
- Lecture 17 (full) (6up): Computability
- Lecture 18 (full) (6up): Counting
- Lecture 19 (full) (6up): Midterm 2 Review (Discrete Math)
- Lecture 20 (full) (6up): Probability Space
- Lecture 21 (full) (6up): Conditional Probability
- Lecture 22 (full) (6up): Bayes Rule
- Lecture 23 (full) (6up): Bayes Rule, Independence
- Lecture 24 (full) (6up): Midterm 2 Review (Probability)
- Lecture 25 (full) (6up): Random Variables
- Lecture 26 (full) (6up): Expectation
- Lecture 27 (full) (6up): Coupons, Independent Random Variables
- Lecture 28 (full) (6up): Variance, Inequalities, WLLN
- Lecture 29 (full) (6up): Confidence Intervals
- Lecture 30 (full) (6up): Linear Regression
- Lecture 31 (full) (6up): Nonlinear Reg., Conditional Exp.
- Lecture 32 (full) (6up): Markov Chain I
- Lecture 33 (full) (6up): Markov Chain II
- Lecture 34 (full) (6up): Continuous Probability I
- Lecture 35 (full) (6up): Continuous Probability II
- Lecture 36 (full) (6up): Continuous Probability II
- Lecture 37 (full) (6up): Gaussian RV, CLT
- Lecture 38 (full) (6up): Random Thoughts
- Lecture 39 (full) (6up): Final Review (Probability)
Expand