back to projects

Randomized Algorithm Suite

Implementations and analysis of QuickSelect and Karger's Min-Cut algorithm with empirical runtime comparisons.

algorithmsresearch
Randomized Algorithm Suite

Overview

A study of expected-case randomized algorithms. QuickSelect achieves O(n) expected time for order statistics; Karger's algorithm finds minimum cuts in O(n² log n) expected time. Includes Monte Carlo repetition analysis and probability of failure bounds.