Karger's algorithm is a randomized algorithm to compute a minimum cut of a connected graph. It works by randomly contracting edges until only two nodes remain, which represent a cut in the original graph. By repeating this process a sufficient number of times, a minimum cut can be found with high probability.

Stanford University

Fall 2022

This course dives into the use of randomness in algorithms and data structures, emphasizing the theoretical foundations of probabilistic analysis. Topics range from tail bounds, Markov chains, to randomized algorithms. The concepts are applied to machine learning, networking, and systems. Prerequisites indicate intermediate-level understanding required.

No concepts data

+ 37 more concepts