Randomized Algorithms
Welcome to Randomized Algorithms
The Lecturers for this course are Prof. Kousha Etessami and Dr. Raul Garcia-Patron.
One of the remarkable developments in Computer Science over the past 30 years has been the realization that the ability of computers to use randomness can lead sometimes to algorithms that are more efficient, conceptually simpler and more elegant that their best-known deterministic counterparts. Randomization has by now become a ubiquitous tool in computation, from applied physics to machine learning.
This course will survey several of the most widely used techniques in this context, illustrating them with examples taken from algorithms, such as Monte Carlo or Gibbs sampling, and combinatorics. Our goal is to provide a solid background in the key ideas used in the design and analysis of randomized algorithms and probabilistic processes.
The required textbook for the course is "Probability and Computing: Randomized Algorithms and Probabilistic Analysis" by Mitzenmacher and Upfal.
Learning Outcomes
On successful completion of this course, you should be able to:
- Understand and apply fundamental tools in discrete probability (e.g. expectation, concentration inequalities, the probabilistic method, random walks) toward the design and analysis of randomized algorithms.
- Understand randomized algorithms for selected combinatorial and graph problems.
- Be able to analyze expected running time and error probabilities of randomized algorithms.
- Understand the fundamentals of Markov chains and their algorithmic applications.
- Apply Monte Carlo methods such as MCMC to some discrete algorithmic problems.
Course Outline
This course is about randomness as a resource in algorithms and computation. The course introduces basic mathematical models and techniques and applies them to the design and analysis of various randomized algorithms. We will also cover a variety of applications of probabilistic ideas and randomization in several areas of computer science.
-Introduction, review of discrete probability, and elementary examples including randomized algorithms for checking identities, matrix multiplication verification, minimum cut in graphs.
-Discrete Random Variables, Moments, Deviations and Tail Inequalities; applications, including the coupon collector problem.
-Chernoff bounds and applications: random sampling and estimation of discrete distributions. The birthday paradox and applications.
-The Probabilistic Method: random graphs and threshold phenomena. Max-cut approximation. Lovasz Local Lemma and application to boolean satisfiability.
-Random Walks and Markov Chains: hitting and cover times; stationary distributions, random walks on undirected graphs.
-The Monte Carlo Method; applications including sampling and approximate counting, the markov chain monte carlo method, the Metropolis algorithm.
-Coupling of Markov Chains, mixing time, and applications, including card shuffling and sampling of graph colourings and independent sets.