Indicator random variables, inversions, randomized algorithms, skip lists, the hiring problem.
Probability theory, computing discrete probabilities, random variables, discrete distribution functions, Bayes’ Theorem, expected values, Central Limit Theorem.
Indicator random variables.
Screencast Suthers 18 min
Inversions
Screencast Suthers 14 min
Randomized algorithms and skip lists
Screencast Suthers 17 min
Analysis of skip lists
Screencast Suthers 8 min
Skip Lists
Screencast Demaine 85 min
The hiring problem, indicator random variable, randomized algorithms
Textbook 16 pages
Skip lists, from Goodrich and Tamassia’s Data Structures and Algorithms in Java
Textbook 10 pages
Probabilistic analysis and randomized algorithms
Notes
Provide four implementations of the Dynamic Set ADT and compare their performance.
Programming