# 随机算法 (Spring 2014)

Randomized Algorithms
Instructor

Email yitong.yin@gmail.com yinyt@nju.edu.cn
office 计算机系 804
Class
Class meetings Tuesday, 10am-12pm

Office hours Wednesday, 2-4pm

Textbooks
Motwani and Raghavan.
Randomized Algorithms.
Cambridge Univ Press, 1995.
Mitzenmacher and Upfal.
Probability and Computing: Randomized Algorithms and Probabilistic Analysis.
Cambridge Univ Press, 2005.
v · d · e

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

# Course info

• Instructor : 尹一通，
• email: yitong.yin@gmail.com, yinyt@nju.edu.cn
• office: 计算机系 804.
• Class meeting: Tuesday 10am-12pm, 仙I-101.
• Office hour: Wednesday 2-4pm, 计算机系 804.

# Syllabus

### 先修课程 Prerequisites

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

### Course materials

• 课程成绩：本课程将会有若干次作业和一次期末考试。最终成绩将由平时作业成绩和期末考试成绩综合得出。
• 迟交：如果有特殊的理由，无法按时完成作业，请提前联系授课老师，给出正当理由。否则迟交的作业将不被接受。

# Lecture Notes

1. Introduction and Probability Space: checking matrix multiplication, polynomial identity testing, communication complexity
2. Conditional Probability: polynomial identity testing, min-cut
3. Random Variables: balls and bins, stable marriage
4. Moment and Deviation: Markov's inequality, Chebyshev's inequality, median selection, random graphs, threshold phenomenon
5. Second Moment: threshold phenomenon for random graphs, 2-point sampling
6. Chernoff Bound: random graphs, threshold phenomenon, Chernoff bound, error reduction, set balancing, packet routing
7. Martingales: martingales, Azuma's inequality, Doob martingales, chromatic number of random graphs
8. Concentration of Measure: bounded difference method, Johnson-Lindenstrauss Theorem
9. Random Recurrence: random quicksort, Karp-Upfal-Wigderson bound
10. The Probabilistic Method: MAX-SAT, conditional probability method, Lovász Local Lemma
11. Universal Hashing: $\displaystyle{ k }$-wise independence, universal hash families, perfect hashing
12. The Monte Carlo Method: counting DNF, the union of sets problem, the coverage algorithm, counting matchings
13. Markov Chain and Random Walk: Markov chain, random walk, stationary distribution, convergence of Markov chain, hitting/cover time
14. Expander Graphs and Mixing: expander graphs, graph spectrum, spectral gap, Cheeger's inequality, rapid mixing of expander walk
15. Mixing Time and Coupling: mixing time, coupling lemma, coupling of Markov chain, rapid mixing by coupling

# The Probability Theory Toolkit

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