This page holds the notes and homeworks for the probability part
of the CS 601 course. The list of topics include:
- Definitions - Sample Spaces, Probability, Probability
Induced by Random Variables. Expectation and
Variance. Independence and Pairwise independence. Expectation
and Variance of independent random variables.
- Discrete distributions - Geometric, Bernoulli,
Hypergeometric, Negative Bernoulli. Expectations.
- Indicator Random Variables and their uses in analysis of
probabilistic algorithms - an introduction.
- Tail Inequalities - Markov, Chebyshev, Chernoff
Bounds. Central Limit Theorem (optional).
- Bayes' Theorem
Notes (Draft, Nov 9 2017)
Homework (Due November 16, 2017)
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.