CS237: Probability in Computing

Syllabus

Course syllabus

Reading

Schedule summary

Lectures Topic Reading
Lectures 1, 2
Review: sets, functions.
Schaums Ch. 1
Lectures 3 -- 7
Counting: counting sequences, subsets, permutations.
LLM 15.1.1, 15.2.1, 15.2.3,
15.3 beginning, 15.3.2, 15.3.3,
15.4 beginning, 15.4.1,
15.5 beginning, 15.5.1, 15.5.2,
15.6.1, 15.6.2,
15.8 beginning,
15.9 beginning, 15.9.1, 15.9.2, 15.9.4
Lectures 8 -- 10
Basic probability: probability spaces, set theory and probability, tree diagrams.
LLM 17.1, 17.2, 17.5.1, 17.5.2, 17.5.3
Lectures 11 -- 15
Conditional probability.
LLM 18.1, 18.2, 18.3, 18.4, 18.5 beginning, 18.5.1
Lecture 16
Independence for events.
LLM 18.7, 18.8 beginning, 18.8.2
Lecture 17
Randomized algorithms: testing whether two polynomials are identical.
Mitzenmacher and Upfal Ch. 1
Lectures 18, 19, 22, 23 Discrete random variables and distributions.
LLM 19.1, 19.2,
19.3 beginning, 19.3.1, 19.3.2, 19.3.4
Lectures 24, 26, 27
Expectation of discrete random variables and distributions.
Conditional expectation.
19.4 beginning, 19.4.4, 19.4.5, 19.4.6
19.5 beginning, 19.5.1, 19.5.2, 19.5.3, 19.5.4
Lectures 28 -- 31
Continuous random variables and distributions.
Independence.
Expectation.
Conditional probability and conditional expectation.
Class notes
Lectures 32, 33
Variance.
LLM 20.2 beginning, 20.2.1, 20.2.2
20.3.1, 20.3.2, 20.3.3, 20.3.4
Lectures 34 -- 37
Parameter estimation and hypothesis testing.
Class notes
Lectures 34, 38
Concentration inequalities: Markov, Chebyshev, Chernoff
LLM 20.1 beginning, 20.1.1, 20.2 beginning, 20.4,
20.6.2, 20.6.3, 20.6.5, 20.6.7

Exercise sheets

Sheet Topic
Sheet 1
Review (sets, sequences, etc.), Counting
Sheet 2
Basic Probability
Sheet 3
Conditional Probability and Independence
Sheet 4
Discrete Random Variables and Distributions
Sheet 5
Discrete Distributions and Expectation
Sheet 6
Continuous Random Variables
Sheet 7
Continuous Random Variables and Distributions
Sheet 8
Normal Distribution, Central Limit Theorem
Sheet 9
Hypothesis Testing

Labs

Lab Topic Files
Lab 1
Python, Basic Probability and R
Lab 1 files
Lab 2
Bloom Filters
Lab 2 files
Lab 3
A Survey of Elementary Distributions through the lens of Bitcoin
Lab 3 files
Lab 4
Second Moment Estimation and Load Balancing
Lab 4 files
Lab 5
Hypothesis Testing and Linear Regression
Lab 5 files

Detailed schedule

Lecture Topic Reading
Lecture 1
Introduction.
Course syllabus
Lectures 2,3
Sets, set operations.
Schaum's Ch. 1
Lecture 4
Functions and counting sequences.
Counting rules: bijection rule, product rule, sum rule.
LLM 15.1.1, 15.2.1, 15.2.3
Lecture 5
Counting rules continued: generalized product rule, division rule.
LLM 15.3 beginning, 15.3.2, 15.4 beginning, 15.4.1
Lecture 6
Counting subsets, permutations.
LLM 15.3.3, 15.5 beginning, 15.5.1
Lecture 7
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
Lecture 8
Basic probability: probability spaces, set theory and probability.
LLM 17.5.1
Lectures 9, 10
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
Lecture 11
Conditional probability and independence.
LLM 18.1, 18.2
Lecture 12
Tree diagram method for conditional probability.
Best-of-three hockey tournament.
Why tree diagrams work.
Medical testing.
LLM 18.3, 18.4
Lecture 13
Medical testing continued.
A posteriori probabilities, Bayes rule.
LLM 18.4.2, 18.4.3, 18.4.4, 18.4.5
Lecture 14
The law of total probability.
LLM 18.5 beginning
Lecture 15
Conditioning on a single event: probability rules from set theory.
LLM 18.5.1
Lecture 16
Independence, mutual independence, k-wise independence.
LLM 18.7, 18.8 beginning, 18.8.2
Lecture 17
Randomized algorithms: testing whether two polynomials are identical.
Mitzenmacher and Upfal Ch. 1
Lectures 18, 19
Discrete random variables.
Indicator random variables and events.
Independence, mutual independence.
Distribution functions (PDF, CDF).
LLM 19.1, 19.2, 19.3 beginning
Lectures 20, 21
Midterm review.
Lectures 22, 23
Discrete distributions: Bernoulli, Uniform. Binomial, Geometric.
LLM 19.3.1, 19.3.2, 19.3.4
Lecture 24
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
Lecture 25
Discuss midterm solutions.
Model midterm solutions posted on Piazza
Lecture 26
Conditional expectation, law of total expectation.
LLM 19.4.5
Lecture 27
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
Lecture 28
Continuous random variables: PDF and CDF.
Continuous random variable that is uniform over an interval.
Discrete vs. continuous vs. mixed random variables.
Class notes
Lecture 29
Playing darts: more examples of discrete, continuous, mixed random variables.
Class notes
Lecture 30
Independence.
Expectation.
Conditional probability and conditional expectation.
Continuous distributions: Uniform and Exponential.
Class notes
Lecture 31
Exponential distribution: connection to Geometric, expectation, memoryless property.
Normal distribution.
Class notes
Lecture 32
Normal distribution: sending bits across noisy channels, standardization.
Variance and standard deviation.
Class notes
LLM 20.2 beginning, 20.2.1, 20.2.2.
Lecture 33
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.
Lecture 34, 35
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
Lectures 36, 37
Hypothesis testing.
Hypothesis testing section in the class notes
Lecture 38
Chernoff Inequality and applications.
LLM 20.6.2, 20.6.3, 20.6.5, 20.6.7
Lectures 39, 40
Final exam review.