CMPS 290A - Winter 2008
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, Talagrands inequality and Applications, Introduction to Markov Chain Monte Carlo, Approximate Counting, Coupling, Sampling Graph Colorings, Canonical Paths, Computing the Permanent of a Matrix.
