Randomized Algorithms (Spring 2010)

随机算法 Randomized Algorithms

Randomized Algorithms by Motwani and Raghavan
Instructor
尹一通
Email	yitong.yin@gmail.com yinyt@nju.edu.cn yinyt@lamda.nju.edu.cn
office	蒙民伟楼 406
Class
Class meetings	10 am-12 am, Tuesday, 馆III-101
Office hours	2pm-5pm, Saturday, MMW 406
Textbook
Motwani and Raghavan, Randomized Algorithms. Cambridge Univ Press, 1995.

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

• (05/26/2010) 第十三课中的Estimator Theorem中有一处笔误，[math]\displaystyle{ \epsilon }[/math]应为[math]\displaystyle{ \epsilon^2 }[/math]。感谢钱超同学发现这个问题。
• (05/25/2010) 第十三课的slides已上传。
• (05/20/2010) 由于老师出差，本周officie hour推迟至周日下午。
• (05/18/2010) The fourth homework assignment is out.
• (05/18/2010) 第十二课的slides已上传。
• (05/10/2010) 第十一课的slides已上传。
• (05/05/2010) 第三次作业没交的同学，请务必在周末（5月8日）之前把作业交到办公室。
• (05/03/2010) 第十课的slides已上传。
• (05/03/2010) 前两次作业的学生名单已公布。 如果交了前两次作业但没有看到名字，请与我联系。
• (04/22/2010) 由于老师外出，本周officie hour取消。
• (04/21/2010) 第二次作业答案已公布。
• (04/21/2010) 第八课的slides已上传。
• (04/20/2010) The third homework assignment is out.
• (04/12/2010) 第七课的slides已上传。
• (04/09/2010) 第六次课的slides中关于k-wise independence fools k-degree polynomials的定理有一个错误，已改正。 感谢王祥丰和钱超两位同学发现这个问题。
• (04/05/2010) 第六课的slides已上传。
• (04/03/2010) 第一次作业答案已公布。
• (03/29/2010) 第五课的slides已上传。
• (03/25/2010) 由于要参加讨论班，本周六（3月27日）下午的office hour改为周日下午。
• (03/22/2010) 第四课的slides已上传。print version是白色背景，方便打印。
• (03/16/2010) The first homework assignment is out.
• (03/15/2010) 通知：从明天（3月16日）开始，教室改为馆III-101，时间不变。
• (03/15/2010) 第三课的slides已上传。
• (03/08/2010) 第二课的slides已上传。
• (03/02/2010) 第一课的slides已上传，见lecture notes部分。pdf文件很大，请先下载再看，尽量不要直接在浏览器打开，可能会引起浏览器长时间失去响应
• (01/21/2010) 上课时间已改为 每周二的第三、四节。请选课的同学们注意。

Syllabus

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

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

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

先修课程 Prerequisites

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

Course materials

• 教材和参考书清单

Policies

• Policies

Assignments

• (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. 中英文不限。

Solutions

• (04/20/2010) Solutions to Problem Set 2.
• (04/03/2010) Solutions to Problem Set 1.

学生名单

前两次作业学生名单

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 | slides | print version
13. Approximate counting, linear programming | slides | print version
14. Randomized approximation algorithms
15. Fingerprinting
16. Number theory algorithms
17. Distributed Algorithms
18. Data streams

The Probability Theory Toolkit

• Linearity of expectation (introduced in Lecture Notes 1, 3)
• Independent events and conditional independence (introduced in Lecture Notes 3)
• Conditional probability and conditional expectation (introduced in Lecture Notes 3)
• The law of total probability and the law of total expectation (introduced in Lecture Notes 2, 3)
• The union bound (introduced in Lecture Notes 3)
• Bernoulli trials (introduced in Lecture Notes 3)
• Geometric distribution (introduced in Lecture Notes 3)
• Binomial distribution (introduced in Lecture Notes 3, 4)
• Markov's inequality (introduced in Lecture Notes 4)
• Chebyshev's inequality (introduced in Lecture Notes 4)
• Chernoff bound (introduced in Lecture Notes 4)
• k-wise independence (introduced in Lecture Notes 6)
• Martingale (introduced in Lecture Notes 7)
• Azuma's inequality and Hoeffding's inequality (introduced in Lecture Notes 7)
• Doob martingale (introduced in Lecture Notes 7)
• The probabilistic method (introduced in Lecture Notes 8)
• The Lovász local lemma and the algorithmic Lovász local lemma (introduced in Lecture Notes 8)
• Markov chain: 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.