# CS237: Probability in Computing

## Lectures

Lecture Topic Lecture Notes
Lecture 1
Introduction, Monty Hall, probability spaces and examples.
Notes
Lecture 2
More examples of probability spaces, review of sets, probability rules from set theory.
Notes
Lecture 3
Review of sets (from CS 131), probability rules from set theory.
Notes
Lecture 4
Review of counting (from CS 131).
Notes
Lecture 5
Review of counting (from CS 131), continuous probability spaces.
Notes
Lecture 6
More examples of continuous probability spaces.
Notes
Lecture 7
Conditional probability.
Notes
Lecture 8
Why tree diagrams work, product rule for conditional probability, law of total probability.
Notes
Lecture 9
Independence.
Notes
Lecture 10
Conditional independence. Probabilities of independent coin flips.
Notes
The material covered by the midterm ends here.
Lecture 11
Review of asymptotic notation (from CS 131). Introduction to randomized algorithms: testing whether two polynomials are equivalent.
Notes
Lecture 12
Introduction to discrete random variables. Independence for random variables.
Notes
Lecture 13
PDF and CDF of a discrete random variable. Discrete distributions: Bernoulli, Uniform, Binomial.
Notes
Lecture 14
Expectation of a discrete random variable. Conditional expectation and law of total expectation. Geometric distribution.
Notes
Lecture 15
Geometric distribution: memoryless property, expectation. Linearity of Expectation.
Lecture 16
Expectation of a Binomial random variable. Coupon collector problem. Functions of random variables.
Notes
Lecture 17
Variance and standard deviation.
Lecture 18
Variance of discrete distributions. Deviations from the mean: Markov and Chebyshev inequalities.
Lecture 19
Applications of Chebyshev: matching birthdays, polling. Estimation by sampling.
Notes
Lecture 20
Pairwise independent sampling. Chernoff Inequality and application to randomized load balancing.
Notes
Lecture 21
Continuous random variables. Continuous distributions: Uniform, Exponential.
Notes
Lecture 22
Expectation, variance, and independence for continuous random variables. Uniform and Exponential distributions continued.
Lecture 23
Uniform and Exponential distributions continued.
Lecture 24
Normal distribution.
The material covered by the final exam ends here.
Lecture 25
Course recap.