CS 70 at UC Berkeley

# Discrete Mathematics and Probability Theory

Lectures: TuTh 12:30-2 pm, 150 Wheeler

### Week 0 Overview

## Propositional Logic, Proofs

### Week 1 Overview

## Induction, Stable Marriage

### Week 2 Overview

## Graph Theory

- Note 5 : Graph Theory
- Discussion 02a (solution)
- Discussion 02b (solution)
- Homework 02 (TeX) (solution)
- Lecture 5 (full) (6up) (webcast)
- Lecture 6 (full) (6up) (webcast)

### Week 3 Overview

## Modular Arithmetic

- Note 6 : Modular Arithmetic
- Discussion 03a (solution)
- Discussion 03b (solution)
- Homework 03 (TeX) (solution)
- Homework 04 (TeX) (solution)
- Lecture 7 (full) (6up) (webcast)
- Lecture 8 (full) (6up) (webcast)

### Week 4 Overview

## Midterm 1, RSA

### Week 5 Overview

## Polynomials, Error Correcting Codes

### Week 6 Overview

## Uncountability, Uncomputability, Counting

### Week 7 Overview

## Probability Spaces, Conditional Probability

### Week 8 Overview

## Random Variables, Distributions

### Week 9 Overview

## Joint Distributions, Linearity of Expectation, Variance

### Week 10 Overview

## Joint Distributions, Continuous Probability

- Note 20 : Continuous Probability
- Discussion 10a (solution)
- Discussion 10b (solution)
- Homework 10 (TeX) (solution)
- Lecture 20 (webcast)
- Lecture 21 (webcast)

### Week 11 Overview

## Continuous Distributions, Gaussians

- Note 20 : Continuous Probability
- Discussion 11a (solution)
- Discussion 11b (solution)
- Homework 11 (TeX) (solution)
- Lecture 22 (webcast)
- Lecture 23 (webcast)

### Week 12 Overview

## Inequalities, Confidence Intervals, Estimation

- Note 18 : Chebyshev's Inequality
- Note 20 : Continuous Probability
- Note 26 : Estimation
- Discussion 12a (solution)
- Discussion 12b (solution)
- Homework 12 (TeX) (solution)
- Lecture 24 (webcast)
- Lecture 25 (webcast)

### Week 13 Overview

## Markov Chains

- Note 24 : Markov Chains
- Note 26 : Estimation
- Discussion 13a (solution)
- Discussion 13b
- Homework 13 (TeX)
- Lecture 26 (webcast)
- Lecture 27

## 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 4: Stable Marriage (PDF)
- Note 5: Graph Theory (PDF)
- Note 6: Modular Arithmetic (PDF)
- Note 7: Bijections and RSA (PDF)
- Note 8: Polynomials (PDF)
- Note 9: Error Correcting Codes (PDF)
- Note 10: Infinity and Uncountability (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)

## 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 00a: Propositional Logic (solution)
- Discussion 00b: Proofs (solution)
- Discussion 01a: Induction (solution)
- Discussion 01b: Stable Marriage (solution)
- Discussion 02a: Graph Theory I (solution)
- Discussion 02b: Graph Theory II (solution)
- Discussion 03a: Modular Arithmetic I (solution)
- Discussion 03b: Modular Arithmetic II, Bijections (solution)
- Discussion 04b: RSA (solution)
- Discussion 05a: Polynomials, Secret Sharing (solution)
- Discussion 05b: Error-Correcting Codes, Berlekamp Welch (solution)
- Discussion 06a: Countability, Computability (solution)
- Discussion 06b: Counting (solution)
- Discussion 07a: Probability Spaces (solution)
- Discussion 07b: Conditional Probability (solution)
- Discussion 08a: Union Bound, Inclusion-Exclusion (solution)
- Discussion 08b: Random Variables (solution)
- Discussion 09a: Expectation, Linearity (solution)
- Discussion 09b: Geometric, Poisson, Variance (solution)
- Discussion 10a: Variance, Joint Distributions (solution)
- Discussion 10b: Joint Distributions, Continuous Probability I (solution)
- Discussion 11a: Joint Continuous Distributions, Uniform/Exponential (solution)
- Discussion 11b: Gaussian Distributions (solution)
- Discussion 12a: Markov's/Chebyshev's Inequalities, WLLN (solution)
- Discussion 12b: LLSE, MMSE (solution)
- Discussion 13a: Continuous Estimation, Markov Chains (solution)
- Discussion 13b: Markov Chains II, Fun

## Homeworks

All 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. **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) (solution)
- Homework 01: Propositional Logic, Proofs, Induction (TeX) (solution)
- Homework 02: Induction, Stable Marriage, Graph Theory (TeX) (solution)
- Homework 03: Graph Theory, Modular Arithmetic (TeX) (solution)
- Homework 04: Modular Arithmetic (TeX) (solution)
- Homework 05: RSA, Polynomials (TeX) (solution)
- Homework 06: Secret Sharing, Error Correcting, Countability (TeX) (solution)
- Homework 07: Countability, Computability, Counting (TeX) (solution)
- Homework 08: Combinatorial Proofs, Probability (TeX) (solution)
- Homework 09: Random Variables, Distributions (TeX) (solution)
- Homework 10: Geometric, Poisson, Variance, Joint Distributions (TeX) (solution)
- Homework 11: Joint Distributions, Continuous Probability (TeX) (solution)
- Homework 12: Conditional Continuous Distributions, Gaussians, Markov's/Chebyshev's Inequalities (TeX) (solution)
- Homework 13: Estimation, Markov Chains (TeX)

## Lecture Slides

- Lecture 1: Introduction, Propositional Logic (full) (6up) (webcast)
- Lecture 2: Proofs/Induction (full) (6up) (webcast)
- Lecture 3: Induction. (full) (6up) (webcast)
- Lecture 4: Induction/Stable Marriage (full) (6up) (webcast)
- Lecture 5: Graphs (full) (6up) (webcast)
- Lecture 6: More Graphs (full) (6up) (webcast)
- Lecture 7: Modular Arithmetic (full) (6up) (webcast)
- Lecture 8: Euclid/CRT/MT Review (full) (6up) (webcast)
- Lecture 9: RSA (full) (6up) (webcast)
- Lecture 10: Secrets and Errors (full) (6up) (webcast)
- Lecture 11: Corruptions (full) (6up) (webcast)
- Lecture 12: Countability/Undecidability (full) (6up) (webcast)
- Lecture 13: Counting (full) (6up) (webcast)
- Lecture 14: Probability (full) (6up) (webcast)
- Lecture 15: Conditional Probability, Bayes (full) (6up) (webcast)
- Lecture 16: Probability, Union Bound (webcast)
- Lecture 17: Conditional Probability, Binomial Distribution (webcast)
- Lecture 18: Random Variables, Expectation, Geomtric Distribution (webcast)
- Lecture 19: Geometric/Poisson Distributions, Variance (webcast)
- Lecture 20: Joint/Conditional Distributions, Intro to Continuous Probability (webcast)
- Lecture 21: Continuous PDFs/CDFs, Uniform/Exponential Distributions (webcast)
- Lecture 22: Exponential Distributions, Joint Continuous Distributions (webcast)
- Lecture 23: Conditional Continuous Distributions, Gaussians (webcast)
- Lecture 24: Gaussians, Markov's/Chebyshev's Inequalities (webcast)
- Lecture 25: LLSE (webcast)
- Lecture 26: Conditional Expectation, Markov Chains (webcast)
- Lecture 27: Markov Chains