Introduction To
Randomized Algorithms
A Randomized Algorithm is an algorithm that employs a degree of randomness as part of its logic. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performance in the "average case" over all possible choices of random bits. Formally, the algorithm's performance will be a random variable determined by the random bits; thus either the running time, or the output (or both) are random variables.
In common practice, randomized algorithms are approximated using a pseudorandom number generator in place of a true source of random bits, such an implementation may deviate from the expected theoretical behavior.
Course Structure
Randomized Algorithms
- Mathematics | Random Variables
- Randomized Algorithms | Set 0 (Mathematical Background)
- Randomized Algorithms | Set 1 (Introduction and Analysis)
- Randomized Algorithms | Set 2 (Classification and Applications)
- Randomized Algorithms | Set 3 (1/2 Approximate Median)
- Binomial Random Variables
- Generate integer from 1 to 7 with equal probability
- Make a fair coin from a biased coin
- Shuffle a given array using Fisher–Yates shuffle Algorithm
- Reservoir Sampling
- Select a random number from stream, with O(1) space
- Random number generator in arbitrary probability distribution fashion
- Write a function that generates one of 3 numbers according to given probabilities
- K’th Smallest/Largest Element in Unsorted Array | Set 2 (Expected Linear Time)
- Birthday Paradox
- Linearity of Expectation
- Expected Number of Trials until Success
- Load Balancing on Servers (Randomized Algorithm)
- Karger’s algorithm for Minimum Cut | Set 1 (Introduction and Implementation)
- Select a Random Node from a Singly Linked List
- Karger’s algorithm for Minimum Cut | Set 2 (Analysis and Applications)
- Primality Test | Set 2 (Fermat Method)
- Generate 0 and 1 with 25% and 75% probability
- Implement rand3() using rand2()
- Strong Password Suggester Program
- Freivald’s Algorithm to check if a matrix is product of two
- Implement random-0-6-Generator using the given random-0-1-Generator
- Select a Random Node from a tree with equal probability
- QuickSort using Random Pivoting
- Operations on Sparse Matrices
- Random Walk (Implementation in Python)
- Expectation or expected value of an array
- Estimating the value of Pi using Monte Carlo
- Randomized Binary Search Algorithm
- Shuffle a deck of cards
- Program to generate CAPTCHA and verify user
- Find an index of maximum occurring element with equal probability
- Implement rand12() using rand6() in one line