CS 601

This page holds the notes and homeworks for the probability part of the CS 601 course. The list of topics include:

1. Definitions - Sample Spaces, Probability, Probability Induced by Random Variables. Expectation and Variance. Independence and Pairwise independence. Expectation and Variance of independent random variables.
2. Discrete distributions - Geometric, Bernoulli, Hypergeometric, Negative Bernoulli. Expectations.
3. Indicator Random Variables and their uses in analysis of probabilistic algorithms - an introduction.
4. Tail Inequalities - Markov, Chebyshev, Chernoff Bounds. Central Limit Theorem (optional).
5. Bayes' Theorem

Notes

Notes (Draft, Nov 9 2017)

Homework

Homework (Due November 16, 2017)

Recommended Books

I have taken the material for the course from

• Introduction to Algorithms by Cormen, Leiserson, Rivest and Stein Appendix C and Chapter 5.
• Probability Theory for Computer Science, Sheldon M. Ross, Chapters 1 and 2.

I recommend doing the exercises in these sources.