随机算法 (Fall 2011)

随机算法 Randomized Algorithms

Randomized Algorithms by Motwani and Raghavan
Instructor
尹一通
Email	yitong.yin@gmail.com yinyt@nju.edu.cn
office	蒙民伟楼 406
Class
Class meetings	TBA TBA
Office hours	TBA
Textbook
Motwani and Raghavan, Randomized Algorithms. Cambridge Univ Press, 1995.

This is the page for the class Randomized Algorithms for the Fall 2011 semester. Students who take this class should check this page periodically for content updates and new announcements.

Announcement

There is no announcement yet.

Course info

• Instructor : 尹一通，

• email: yitong.yin@gmail.com, yinyt@nju.edu.cn
• office: MMW 406.

• Class meeting: TBA.
• Office hour: TBA.

Syllabus

随机化（randomization）是现代计算机科学最重要的方法之一，近二十年来被广泛的应用于计算机科学的各个领域。在这些应用的背后，是一些共通的随机化原理。在随机算法这门课程中，我们将用数学的语言描述这些原理，将会介绍以下内容：

• 一些重要的随机算法的设计思想和理论分析；
• 概率论工具及其在算法分析中的应用，包括常用的概率不等式，以及数学证明的概率方法 (the probabilistic method);
• 随机算法的概率模型，包括典型的随机算法模型，以及概率复杂度模型。

作为一门理论课程，这门课的内容偏重数学上的分析和证明。这么做的目的不单纯是为了追求严格性，而是因为用更聪明的方法去解决问题往往需要具备有一定深度的数学思维和数学洞察力。

先修课程 Prerequisites

• 必须：离散数学，概率论，线性代数。
• 推荐：算法设计与分析。

Course materials

• 教材和参考书清单

Policies

• Policies

Assignments

There is no assignments yet.

Lecture Notes

1. Introduction
   • Randomized Algorithms: an Introduction
   • Complexity Classes
2. Probability Basics
   • Probability Space
   • Verifying Matrix Multiplication
   • Conditional Probability
   • Randomized Min-Cut
   • Random Variables and Expectations
   • Randomized Quicksort
3. Balls and Bins
   • Distributions of Coin Flipping
   • Birthday Problem
   • Coupon Collector
   • Balls-into-balls Occupancy Problem
   • Bloom Filter
   • Stable Marriage
4. Moment and Deviation
   • Markov's Inequality
   • Chebyshev's Inequality
   • Median Selection
   • Random Graphs
5. Hashing and Fingerprinting
   • Pair-wise Independence
   • Derandomization: Two-Point Sampling
6. Chernoff Bound
   • Chernoff Bound
   • Set Balancing
   • DNF Counting
   • Routing in a Parallel Network
7. Concentration of Measure
   • Martingales
   • Azuma's Inequality
   • The Method of Bounded Differences
8. Dimension Reduction
   • Johnson-Lindenstrauss Theorem
   • Locality Sensitive Hashing
9. The Probabilistic Method
   • The Probabilistic Method
   • Lovász Local Lemma
   • Derandomization: Conditional Expectation
   • Derandomization: Color-coding
10. Approximation Algorithms, On-line Algorithms
    • Max-SAT
    • Linear Programming
    • Randomized Rounding
    • On-line Algorithms
11. Markov Chain and Random Walk
    • Markov Chains
    • Random Walks on Undirected Graphs
    • Electrical Network
    • Cover Time
    • Graph Connectivity
12. Random Walk Algorithms
    • Randomized 2SAT
    • Randomized 3SAT
    • Perfect Matching in Regular Bipartite Graph
    • The Metropolis Algorithm
    • Dynamics on Spins
13. Coupling and Mixing Time
    • Mixing Time
    • Coupling
    • Card Shuffling
    • Path Coupling
    • Graph Coloring
14. Expander Graphs I
    • Expander Graphs
    • Graph Spectrum
    • The Spectral Gap
    • Random Walk on Expander Graph
15. Expander Graphs II
    • Expander Mixing Lemma
    • Chernoff Bound for Expander Walks
    • The Zig-Zag Product
    • USTCON in LOGSPACE
16. Sampling and Counting
    • The #P Class and Approximation
    • DNF Counting
    • Canonical Paths
    • Count Matchings
    • Sampling and Counting
17. Markov Chain Monte Carlo (MCMC)
    • Spin Systems
    • Simulated Annealing
    • Volume Estimation
18. Complexity

The Probability Theory Toolkit

• Linearity of expectation
• Independent events and conditional independence
• Conditional probability and conditional expectation
• The law of total probability and the law of total expectation
• The union bound
• Bernoulli trials
• Geometric distribution
• Binomial distribution
• Markov's inequality
• Chebyshev's inequality
• Chernoff bound
• k-wise independence
• Martingale
• Azuma's inequality and Hoeffding's inequality
• Doob martingale
• The probabilistic method
• The Lovász local lemma and the algorithmic Lovász local lemma
• Markov chain:

reducibility, Periodicity, stationary distribution, hitting time, cover time;

mixing time, conductance