CS237: Probability in Computing

Review (sets, sequences, etc.), Counting

Basic Probability

Conditional Probability and Independence

Discrete Random Variables and Distributions

Discrete Distributions and Expectation

Continuous Random Variables

Continuous Random Variables and Distributions

Normal Distribution, Central Limit Theorem

Hypothesis Testing

Python, Basic Probability and R

Bloom Filters

A Survey of Elementary Distributions through the lens of Bitcoin

Second Moment Estimation and Load Balancing

Hypothesis Testing and Linear Regression

Introduction.

Sets, set operations.

Schaum's Ch. 1

Functions and counting sequences.
Counting rules: bijection rule, product rule, sum rule.

LLM 15.1.1, 15.2.1, 15.2.3

Counting rules continued: generalized product rule, division rule.

LLM 15.3 beginning, 15.3.2, 15.4 beginning, 15.4.1

Counting subsets, permutations.

LLM 15.3.3, 15.5 beginning, 15.5.1

Counting bit sequences.
Sequences with repetitions, bookkeeper rule.
Inclusion-exclusion principle.
Pigeonhole principle.

LLM 15.5.2,
15.6.1, 15.6.2,
15.8 beginning,
15.9 beginning, 15.9.1, 15.9.2, 15.9.4

Basic probability: probability spaces, set theory and probability.

LLM 17.5.1

Monty Hall problem, tree diagram method.
Probability rules from set theory, uniform probability spaces.

LLM 17.1, 17.2, 17.5.1, 17.5.2, 17.5.3

Conditional probability and independence.

LLM 18.1, 18.2

Tree diagram method for conditional probability.
Best-of-three hockey tournament.
Why tree diagrams work.
Medical testing.

LLM 18.3, 18.4

Medical testing continued.
A posteriori probabilities, Bayes rule.

LLM 18.4.2, 18.4.3, 18.4.4, 18.4.5

The law of total probability.

LLM 18.5 beginning

Conditioning on a single event: probability rules from set theory.

LLM 18.5.1

Independence, mutual independence, k-wise independence.

LLM 18.7, 18.8 beginning, 18.8.2

Randomized algorithms: testing whether two polynomials are identical.

Mitzenmacher and Upfal Ch. 1

Discrete random variables.
Indicator random variables and events.
Independence, mutual independence.
Distribution functions (PDF, CDF).

LLM 19.1, 19.2, 19.3 beginning

Midterm review.

Discrete distributions: Bernoulli, Uniform. Binomial, Geometric.

LLM 19.3.1, 19.3.2, 19.3.4

Expectation of a discrete random variable.
Expectation of a Bernoulli and Uniform random variable.
Linearity of expectation.

LLM 19.4 beginning, 19.4.4,
19.5 beginning, 19.5.1

Discuss midterm solutions.

Model midterm solutions posted on Piazza

Conditional expectation, law of total expectation.

LLM 19.4.5

Expectation of a Binomial random variable.
Expectation of a Geometric random variable.
The coupon collector problem.

LLM 19.4.6, 19.5.2, 19.5.3, 19.5.4

Continuous random variables: PDF and CDF.
Continuous random variable that is uniform over an interval.
Discrete vs. continuous vs. mixed random variables.

Class notes

Playing darts: more examples of discrete, continuous, mixed random variables.

Class notes

Independence.
Expectation.
Conditional probability and conditional expectation.
Continuous distributions: Uniform and Exponential.

Class notes

Exponential distribution: connection to Geometric, expectation, memoryless property.
Normal distribution.

Class notes

Normal distribution: sending bits across noisy channels, standardization.
Variance and standard deviation.

Class notes
LLM 20.2 beginning, 20.2.1, 20.2.2.

Properties of variance.
Variance of Bernoulli, Geometric, and Binomial random variables.
Variance of a sum of independent random variables.

LLM 20.3.1, 20.3.2, 20.3.3, 20.3.4.

Parameter estimation.
Markov Inequality, Chebyshev Inequality.
Central limit theorem.

Parameter estimation section in the class notes
LLM 20.1 beginning, 20.1.1, 20.2 beginning, 20.4

Hypothesis testing.

Hypothesis testing section in the class notes

Chernoff Inequality and applications.

LLM 20.6.2, 20.6.3, 20.6.5, 20.6.7

Final exam review.