Randomized algorithms and probabilistic analysis

Algorithms whose identity is their use of randomness or whose analysis averages over random inputs: expected running time under input distributions, Fisher-Yates shuffling, the hiring problem, Karger's minimum cut, Freivalds' matrix-product check and MinHash similarity sketches.

• Average-case running time
• Fisher–Yates shuffle
• Freivalds' algorithm
• Hiring problem
• Karger's algorithm
• MinHash and Jaccard similarity

The dependency explorer needs JavaScript and its graph data.

Download the complete graph data.