Engineering - Course - Randomized Algorithms

Introduction to randomization. Las Vegas and Monte Carlo algorithms. Markov and Chebyshev inequalities. Randomized selection. Two-point sampling. Graph applications: minimum spanning trees, minimum cuts. Chernoff bound. The probabilistic method. Random walks.