# Randomized Algorithms (Spring 2010)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Instructor Randomized Algorithms by Motwani and Raghavan 尹一通 yitong.yin@gmail.com yinyt@nju.edu.cn yinyt@lamda.nju.edu.cn 蒙民伟楼 406 10 am-12 am, Tuesday, 馆III-101 2pm-5pm, Saturday, MMW 406 Motwani and Raghavan, Randomized Algorithms. Cambridge Univ Press, 1995. v · d · e

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

There is also a backup page for off-campus users. The URL is http://lamda.nju.edu.cn/yinyt/random2010wiki/

# Announcement

• (07/01/2010) 期末考试：时间7月6日，上午9点至11点；地点：教202。可携带一页A4打印纸（可双面）的笔记。
• (06/26/2010) 由于要统计考试人数，请参加期末考试的同学给我发email，把名字和学号告诉我。请看到通知的同学互相告知一下。
• (06/24/2010) 第四次作业答案公布。第三次作业答案已经补完。Sorry for the delay!
• (06/11/2010) 由于端午节轮休，6月15日的课改在13日星期日。
• (06/01/2010) The fifth homework is out. Due on Tuesday June 15, in class.
• (05/26/2010) 第十三课中的Estimator Theorem中有一处笔误，${\displaystyle \epsilon }$应为${\displaystyle \epsilon ^{2}}$。感谢钱超同学发现这个问题。
(older announcements...)

# Course info

• Instructor : 尹一通，
• email: yitong.yin@gmail.com, yinyt@nju.edu.cn, yinyt@lamda.nju.edu.cn
• office: MMW 406.
• Class meeting: 10am-12 am, Tue; 馆III-101.
• Office hour: 2-5pm, Sat; MMW 406.

# Syllabus

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

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

# Assignments

• (06/29/2010) Problem Set 6 makeup assignment, hand in before the final exam.
• (06/01/2010) Problem Set 5 due on June 15 , Tuesday, in class. 中英文不限。
• (05/18/2010) Problem Set 4 due on June 1 , Tuesday, in class. 中英文不限。
• (04/20/2010) Problem Set 3 due on May 4, Tuesday, in class. 中英文不限。
• (03/30/2010) Problem Set 2 due on April 13, Tuesday, in class. 中英文不限。
• (03/16/2010) Problem Set 1 due on March 30, Tuesday, in class. 中英文不限。

# Lecture Notes

1. Introduction | slides | print version
2. Complexity classes, lower bounds | slides | print version
3. Balls and bins | slides | print version
4. Tail inequalities | slides | print version
5. Set balancing, packet routing, and metric embedding | slides | print version
6. Hashing, limited independence | slides | print version
7. Martingales | slides | print version
8. The probabilistic method | slides | print version
9. [Midterm review, and screening of a documentary film about Paul Erdős]
10. Markov chains and random walks | slides | print version
11. Expander graphs, rapid mixing random walks | slides | print version
12. Random sampling, MCMC | slides | print version
13. Approximate counting, linear programming | slides | print version
14. Randomized approximation algorithms | slides | print version
15. Fingerprinting | slides | print version
16. Guest lecture by Yang Yu on metaheuristics. | slides
17. Distributed algorithms, data streams | slides | print version
18. Review session.

### Future plan

Topics that I'm considering to cover at next time when I teach this class (perhaps):

• Janson's inequality,
• Talagrand's inequality
• The Poisson Approximation
• Fourier analysis
• Random graphs
• Entropy and randomness
• Derandomization
• Color-coding
• On-line algorithms
• Property testing
• Learning and boosting
• Compressed sensing

Feel free to send me an email at any time to tell what topics you would like this class to cover in future.

# The Probability Theory Toolkit

reducibility, Periodicity, stationary distribution, hitting time, cover time, (introduced in Lecture Notes 10);
mixing time, conductance (introduced in Lecture Notes 11 and 12)

# Acknowledgment

Thanks the LAMDA group for hosting the webpage for off-campus users. Special thanks to YU Yang for his time and technical supports.