Topics in Algorithms and Complexity Theory: Probabilistic Algorithms and Average Case Analysis

CMPS 290A Syllabus

Randomized Min-Cut, Moments and Independence, Linearity of  Expectation, First and Second Moment Method, Probability Amplification  via Pairwise Independence, The Method of Deferred decisions,  Randomized Stable Marriage, The Coupons Collector's Problem, Balls in  Bins, The Poisson Approximation, Bloom Filters, Chernoff bounds,  Random Projections, Randomized Rounding, Random Skip Lists, Random  Graph Models, Branching Processes and Generating Functions, The Giant  Component, Hamiltonian Cycles in Random Graphs, Martingales, The Azuma- Hoedffing Inequality, The Chromatic Number of Random Graphs,  Talagrand's inequality and Applications, Introduction to Markov Chain  Monte Carlo, Approximate Counting, Coupling, Sampling Graph Colorings, Canonical Paths, Computing the Permanent of a Matrix.

Instructors and Assistants