Syllabus
Concepts of probability: discrete and continuous sample spaces, random variables, expectation, variance, conditioning, independence.
Randomized algorithms: median finding, minimum cut, hashing, load balancing, sorting, random walks on graphs, streaming and online algorithms.
Stochastic processes: random walks on the line and on a graph; central limit theorem; large deviation bounds; random graph models. Applications in web search, social networks, and the simulation of physical lattices.
Distributional modeling: Binomial, Poisson, Gaussian. Maximum-likelihood estimation. Classification via generative models.
Statistical hypothesis testing. Applications in clinical trials and DNA fingerprinting.
Course materials
1. The required text for this course is:
Grinstead and Snell. Introduction to Probability.
A PDF of it can be downloaded free from the web (here), or you can obtain a hard copy from the American Mathematical Society bookshop.
2. We will cover many topics that aren't in the Grinstead and Snell book. I will post lecture summaries for this additional material.
3. Suggestions for supplementary reading:
Mitzenmacher and Upfal. Probability and Computing.
Duda, Hart, and Stork. Pattern Classification.
Freedman, Pisani, and Purves. Statistics.
Discussion section
Fri 2.00-2.50 on Zoom.
This discussion will reinforce material from lecture as well as background material from earlier courses (like CSE 21). Quizzes might also be held during this time.
Grading
Weekly homework: 30%
Weekly quiz: 40%
Final: 30%
The lowest homework and lowest quiz will be dropped