Introduction to Randomized Algorithms

Introduction to Randomized Algorithms:

Random Variables Binomial 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)...

Easy Problems on Randomized Algorithms:

Write a function that generates one of 3 numbers according to given probabilities Generate 0 and 1 with 25% and 75% probability Implement rand3() using rand2() Birthday Paradox Expectation or expected value of an array Shuffle a deck of cards Program to generate CAPTCHA and verify user Find an index of maximum occurring element with equal probability Randomized Binary Search Algorithm...

Medium Problems on Randomized Algorithms:

Make a fair coin from a biased coin Shuffle a given array using Fisher–Yates shuffle Algorithm Expected Number of Trials until Success Strong Password Suggester Program QuickSort using Random Pivoting Operations on Sparse Matrices Estimating the value of Pi using Monte Carlo Implement rand12() using rand6() in one line...

Hard Problems on Randomized Algorithms:

Generate integer from 1 to 7 with equal probability Implement random-0-6-Generator using the given random-0-1-Generator Select a random number from stream, with O(1) space Random number generator in arbitrary probability distribution fashion Reservoir Sampling Linearity of Expectation Introduction and implementation of Karger’s algorithm for Minimum Cut Select a Random Node from a Singly Linked List Select a Random Node from a tree with equal probability Freivald’s Algorithm to check if a matrix is product of two Random Acyclic Maze Generator with given Entry and Exit point...