Spring 2017 CS70 at UC Berkeley

# Discrete Mathematics and Probability Theory

Lectures: T/Th 12:30 - 2:00 p.m., Pauley Ballroom

## Professor Satish Rao

satishr@eecs (dot) berkeley (dot) edu

Office Hours: M 11-12 p.m., T 4-5 p.m. in Soda 687

### Week 0 Overview

## Propositional Logic and Proofs

### Week 1 Overview

## Proofs, Induction

### Week 2 Overview

## Stable Marriage, Graph Theory

### Week 3 Overview

## Modular Arithmetic, Bijections

### Week 4 Overview

## RSA, Polynomials

### Week 5 Overview

## 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

## Midterm 2

### Week 11 Overview

## Regression, Conditional Expectation

### Week 12 Overview

## Markov Chains, Continuous Probability

### Week 13 Overview

## Continuous Probability

- Note 20 : Continuous Probability
- Discussion 13a
- Discussion 13b
- Homework 13 (Tex)
- Slides 26
- Slides 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
- 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

## 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, Proofs (solution)
- Discussion 00b: Proofs (solution)
- Discussion 01a: Induction (solution)
- Discussion 01b: Stable Marriage (solution)
- Discussion 02a: Graph Theory (solution)
- Discussion 02b: Graph Theory (solution)
- Discussion 03a: Modular Arithmetic (solution)
- Discussion 03b: Modular Arithmetic, Bijections (solution)
- Discussion 04a: Fermat's Little Theorem, RSA (solution)
- Discussion 04b: Polynomials (solution)
- Discussion 05a: Lagrange Interpolation, Erasure Codes, Secret Sharing (solution)
- Discussion 05b: Berlekamp-Welch (solution)
- Discussion 06a: Uncountability, Uncomputability (solution)
- Discussion 06b: Counting (solution)
- Discussion 07a: Basic Probability (solution)
- Discussion 07b: Conditional Probability (solution)
- Discussion 08a: Random Variables, Binomial Distribution (solution)
- Discussion 08b: Union Bound, Geometric Distribution, Poisson Distribution (solution)
- Discussion 09a: Joint Distributions, Linearity of Expectation (solution)
- Discussion 09b: Variance (solution)
- Discussion 10a: Markov's Inequality, Chebyshev's Inequality, WLLN, Confidence Intervals (solution)
- Discussion 11a: Covariance, LLSE (solution)
- Discussion 11b: Regression, Conditional Expectation (solution)
- Discussion 12a: Markov Chains (solution)
- Discussion 12b: Markov Chains, Continuous Probability (solution)
- Discussion 13a: Continuous Probability
- Discussion 13b: Fun

## 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 00: Propositional Logic, Proofs (Tex) (solution)
- Homework 01: Proofs, Induction (Tex) (solution)
- Homework 02: Induction, Stable Marriage, Graph Theory (Tex) (solution)
- Homework 03: Graph Theory (Tex) (solution)
- Homework 04: Modular Arithmetic (Tex) (solution)
- Homework 05: Chinese Remainder Theorem, RSA, Polynomials (Tex) (solution)
- Homework 06: Polynomials, Secret Sharing, Error Correcting Codes, Uncountability (Tex) (solution)
- Homework 07: Uncountability, Uncomputability, Counting (Tex) (solution)
- Homework 08: Combinatorial Proofs, Probability Spaces, Conditional Probability, Independence (Tex) (solution)
- Homework 09: Union Bounds, Geometric Distribution, Poisson Distribution, Joint Distributions (Tex) (solution)
- Homework 10: Expectation, Variance, Inequalities, Confidence Intervals (Tex) (solution)
- Homework 12: Regression, Conditional Expectation (Tex) (solution)
- Homework 13: Markov Chains, Continuous Probability (Tex)

## 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): Stable Marriage Algorithm.
- Lecture 5 (full) (6up): Graphs, Eulerian Tours, and Planar Graphs.
- Lecture 6 (full) (6up): Graphs, Coloring, Types of Graphs.
- Lecture 7 (full) (6up): Modular Arithmetic.
- Lecture 8 (full) (6up): Modular Arithmetic, Review.
- Lecture 9 (full) (6up): RSA.
- Lecture 10 (full) (6up): Polynomials, Secret Sharing, Coding.
- Lecture 11 (full) (6up): Berlekamp-Welch.
- Lecture 12 (full) (6up): Countability, Uncountability.
- Lecture 13 (full) (6up): Undecidability.
- Lecture 14 (full) (6up): Counting.
- Lecture 15 (full) (6up): Counting, Probability.
- Lecture 16 (full) (6up): Conditional Probability, Independence.
- Lecture 17 (full) (6up): Bayes Rule, Coupon Collector.
- Lecture 18 (full) (6up): Random Variables, Distributions, Expectation. (Draft)
- Lecture 19 (full) (6up): Linearity of Expectation.
- Lecture 20 (full) (6up): Coupons, Variance, Markov.
- Lecture 21 (full) (6up): Variance, Midterm Review. (Draft)
- Lecture 22 (full) (6up): Confidence Intervals, Linear Regression.
- Lecture 23 (full) (6up): Conditional Expectation: MMSE. (Draft)
- Lecture 24 (full) (6up): Markov Chains.
- Lecture 25 (full) (6up): Markov Chains, Continuous. (Draft)
- Slide 26:
- Slide 27: