Probabilistic Combinatorics and Algorithms II

4 credits

Introduction to probabilistic algorithms. Game theoretic techniques. Applications of the probabilistic method to algorithm analysis. Markov Chains and Random walks. Applications to approximation algorithms, distributed algorithms, online and parallel algorithms. MATH 261A must be taken before MATH 261B. Prerequisites: MATH 261A.