Module: Probabilistic Analysis

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

Learning Outcomes

Understand probabilistic analysis.

Understand when and how to analyze an algorithm based on a distribution of the probability of each case.

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