# 随机算法 (Spring 2013)

Jump to: navigation, search

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 2013 semester. Students who take this class should check this page periodically for content updates and new announcements.

# Announcement

• 所有slides已经上传。
• The last homework assignment is out, due on the date of the final exam.
• 前几堂课的讲义已经补上，足够完成第三次作业。
• The third homework assignment is out, due in two weeks.
• The second homework assignment is out, due in two weeks.
• 第1次作业第3题新增一问。由于是在作业发布之后修改，是否做这一问题不会影响分数，但增加此问会使该题目更有意义。
• The first homework assignment is out, due in two weeks.

# Course info

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

# Syllabus

### 先修课程 Prerequisites

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

### 成绩 Grades

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

# Lecture Notes

Slides: 1| 3| 4| 5| 6| 7| 8| 9| 10| 11| 12| 13| 14| 15| 16| 17

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

# The Probability Theory Toolkit

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