Module: Probabilistic Analysis

Indicator random variables, inversions, randomized algorithms, skip lists, the hiring problem.

Prerequisite Modules

Discrete probability

Probability theory, computing discrete probabilities, random variables, discrete distribution functions, Bayes’ Theorem, expected values, Central Limit Theorem.

Learning Outcomes

Carry out probabilistic analysis, including:

Use of indicator random variables to characterize expected values.

Readings

Indicator random variables

Indicator random variables.

Screencast Suthers 18 min

Example analysis: inversions

Inversions

Screencast Suthers 14 min

Randomized algorithms and skip lists

Randomized algorithms and skip lists

Screencast Suthers 17 min

Analysis of skip lists

Analysis of skip lists

Screencast Suthers 8 min

Skip Lists

Skip Lists

Screencast Demaine 85 min

CLRS 5 - Probabilistic Analysis and Randomized Algorithms

The hiring problem, indicator random variable, randomized algorithms

Textbook 16 pages

Skip Lists in Java

Skip lists, from Goodrich and Tamassia’s Data Structures and Algorithms in Java

Textbook 10 pages

Chapter 5 Notes

Probabilistic analysis and randomized algorithms

Notes

Experiential Learning

Battle of the Dynamic Sets

Provide four implementations of the Dynamic Set ADT and compare their performance.

Programming