Randomized Algorithms (Spring 2010): Difference between revisions

From TCS Wiki
Jump to navigation Jump to search
← Older edit
VisualWikitext
imported>WikiSysop
imported>WikiSysop
 
(100 intermediate revisions by the same user not shown)
Line 31: Line 31:
|header6 =
|header6 =
|label6  = Class meetings
|label6  = Class meetings
|data6  = 10 am-12 am, Tuesday, <br><font color="red" size="3">馆III-101</font>
|data6  = 10 am-12 am, Tuesday, <br>馆III-101
|header7 =
|header7 =
|label7  = Place
|label7  = Place
Line 54: Line 54:


= Announcement =  
= Announcement =  
* (04/21/2010) <font size ="5" color="red">第二次作业答案已公布。</font>
* (07/01/2010) 期末考试：时间7月6日，上午9点至11点；地点：教202。可携带一页A4打印纸（可双面）的笔记。
* (04/21/2010) <font size ="5" color="red">第八课的slides已上传。</font>
* (06/26/2010) 由于要统计考试人数，请参加期末考试的同学给我发email，把名字和学号告诉我。请看到通知的同学互相告知一下。
* (04/20/2010)<font size ="5" color="red">The third homework assignment is out.</font>
* (06/24/2010) 第四次作业答案公布。第三次作业答案已经补完。Sorry for the delay!
* (04/12/2010) 第七课的slides已上传。
* (06/11/2010) 由于端午节轮休，6月15日的课改在13日星期日。
* (04/09/2010) 第六次课的slides中关于k-wise independence fools k-degree polynomials的定理有一个错误，已改正。 感谢王祥丰和钱超两位同学发现这个问题。
* (06/01/2010) The fifth homework is out. Due on Tuesday June 15, in class.
* (04/05/2010) 第六课的slides已上传。
* (05/26/2010) 第十三课中的Estimator Theorem中有一处笔误，<math>\epsilon</math>应为<math>\epsilon^2</math>。感谢钱超同学发现这个问题。
* (04/03/2010) 第一次作业答案已公布。
::[[Randomized_Algorithms_(Spring_2010)/class announcements|(''older announcements...'')]]
* (03/29/2010) 第五课的slides已上传。
 
* (03/25/2010) 由于要参加讨论班，本周六（3月27日）下午的office hour改为周日下午。
= Course info =
* (03/22/2010) 第四课的slides已上传。print version是白色背景，方便打印。
* '''Instructor ''': 尹一通，
* (03/16/2010) The first homework assignment is out.
:*email: yitong.yin@gmail.com, yinyt@nju.edu.cn, yinyt@lamda.nju.edu.cn
* (03/15/2010) 通知：从明天（3月16日）开始，教室改为馆III-101，时间不变。
:*office: MMW 406.
* (03/15/2010) 第三课的slides已上传。
* '''Class meeting''': 10am-12 am, Tue; 馆III-101.
* (03/08/2010) 第二课的slides已上传。
* '''Office hour''': 2-5pm, Sat; MMW 406.
* (03/02/2010) 第一课的slides已上传，见lecture notes部分。pdf文件很大，请先下载再看，尽量不要直接在浏览器打开，可能会引起浏览器长时间失去响应
* (01/21/2010) 上课时间已改为 每周二的第三、四节。请选课的同学们注意。


= Syllabus =
= Syllabus =
Line 89: Line 87:


= Assignments =
= Assignments =
* (06/29/2010) [[Randomized Algorithms (Spring 2010)/Problem Set 6 | Problem Set 6]] makeup assignment, hand in before the final exam.
* (06/01/2010) [[Randomized Algorithms (Spring 2010)/Problem Set 5 | Problem Set 5]] due on June 15 , Tuesday, in class. 中英文不限。
* (05/18/2010) [[Randomized Algorithms (Spring 2010)/Problem Set 4 | Problem Set 4]] due on June 1 , Tuesday, in class. 中英文不限。
* (04/20/2010) [[Randomized Algorithms (Spring 2010)/Problem Set 3 | Problem Set 3]] due on May 4, Tuesday, in class. 中英文不限。
* (04/20/2010) [[Randomized Algorithms (Spring 2010)/Problem Set 3 | Problem Set 3]] due on May 4, Tuesday, in class. 中英文不限。
* (03/30/2010) [[Randomized Algorithms (Spring 2010)/Problem Set 2 | Problem Set 2]] due on April 13, Tuesday, in class. 中英文不限。
* (03/30/2010) [[Randomized Algorithms (Spring 2010)/Problem Set 2 | Problem Set 2]] due on April 13, Tuesday, in class. 中英文不限。
* (03/16/2010) [[Randomized Algorithms (Spring 2010)/Problem Set 1 | Problem Set 1]] due on March 30, Tuesday, in class. 中英文不限。
* (03/16/2010) [[Randomized Algorithms (Spring 2010)/Problem Set 1 | Problem Set 1]] due on March 30, Tuesday, in class. 中英文不限。
=== Solutions ===
* (04/20/2010) [[Randomized_Algorithms_(Spring_2010)/Solutions_to_PS2 | Solutions to Problem Set 2]].
* (04/03/2010) [[Randomized_Algorithms_(Spring_2010)/Solutions_to_PS1 | Solutions to Problem Set 1]].


= Lecture Notes =
= Lecture Notes =
# [[Randomized Algorithms (Spring 2010)/Introduction|Introduction]] | [http://lamda.nju.edu.cn/yinyt/notes/random1.pdf slides]
# [[Randomized Algorithms (Spring 2010)/Introduction|Introduction]] | [http://lamda.nju.edu.cn/yinyt/notes/random1.pdf slides] | [http://lamda.nju.edu.cn/yinyt/notes/random1-print.pdf print version]
# [[Randomized Algorithms (Spring 2010)/Complexity classes and lower bounds|Complexity classes, lower bounds]] | [http://lamda.nju.edu.cn/yinyt/notes/random2.pdf slides]
# [[Randomized Algorithms (Spring 2010)/Complexity classes and lower bounds|Complexity classes, lower bounds]] | [http://lamda.nju.edu.cn/yinyt/notes/random2.pdf slides] | [http://lamda.nju.edu.cn/yinyt/notes/random2-print.pdf print version]
# [[Randomized Algorithms (Spring 2010)/Balls and bins|Balls and bins]] | [http://lamda.nju.edu.cn/yinyt/notes/random3.pdf slides] | [http://lamda.nju.edu.cn/yinyt/notes/random3-print.pdf print version]
# [[Randomized Algorithms (Spring 2010)/Balls and bins|Balls and bins]] | [http://lamda.nju.edu.cn/yinyt/notes/random3.pdf slides] | [http://lamda.nju.edu.cn/yinyt/notes/random3-print.pdf print version]
# [[Randomized Algorithms (Spring 2010)/Tail inequalities|Tail inequalities]] | [http://lamda.nju.edu.cn/yinyt/notes/random4.pdf slides] | [http://lamda.nju.edu.cn/yinyt/notes/random4-print.pdf print version]
# [[Randomized Algorithms (Spring 2010)/Tail inequalities|Tail inequalities]] | [http://lamda.nju.edu.cn/yinyt/notes/random4.pdf slides] | [http://lamda.nju.edu.cn/yinyt/notes/random4-print.pdf print version]
Line 107: Line 104:
# [[Randomized Algorithms (Spring 2010)/The probabilistic method | The probabilistic method]] | [http://lamda.nju.edu.cn/yinyt/notes/random8.pdf slides] | [http://lamda.nju.edu.cn/yinyt/notes/random8-print.pdf print version]
# [[Randomized Algorithms (Spring 2010)/The probabilistic method | The probabilistic method]] | [http://lamda.nju.edu.cn/yinyt/notes/random8.pdf slides] | [http://lamda.nju.edu.cn/yinyt/notes/random8-print.pdf print version]
# <nowiki>[</nowiki>Midterm review, and screening of a documentary film about Paul Erdős<nowiki>]</nowiki>
# <nowiki>[</nowiki>Midterm review, and screening of a documentary film about Paul Erdős<nowiki>]</nowiki>
# [[Randomized Algorithms (Spring 2010)/Markov chains and random walks | Markov chains and random walks]]
# [[Randomized Algorithms (Spring 2010)/Markov chains and random walks | Markov chains and random walks]] | [http://lamda.nju.edu.cn/yinyt/notes/random10.pdf slides] | [http://lamda.nju.edu.cn/yinyt/notes/random10-print.pdf print version]
# Random sampling
# [[Randomized Algorithms (Spring 2010)/Expander graphs and rapid mixing random walks | Expander graphs, rapid mixing random walks]] | [http://lamda.nju.edu.cn/yinyt/notes/random11.pdf slides] | [http://lamda.nju.edu.cn/yinyt/notes/random11-print.pdf print version]
# Approximate counting
# [[Randomized Algorithms (Spring 2010)/Random sampling | Random sampling, MCMC]] | [http://lamda.nju.edu.cn/yinyt/notes/random12.pdf slides] | [http://lamda.nju.edu.cn/yinyt/notes/random12-print.pdf print version]
# Geometric algorithms and linear programming
# [[Randomized Algorithms (Spring 2010)/Approximate counting, linear programming|Approximate counting, linear programming]] | [http://lamda.nju.edu.cn/yinyt/notes/random13.pdf slides] | [http://lamda.nju.edu.cn/yinyt/notes/random13-print.pdf print version]
# Random graphs, graph algorithms
# [[Randomized Algorithms (Spring 2010)/Randomized approximation algorithms|Randomized approximation algorithms]] | [http://lamda.nju.edu.cn/yinyt/notes/random14.pdf slides] | [http://lamda.nju.edu.cn/yinyt/notes/random14-print.pdf print version]
# Fingerprinting
# [[Randomized Algorithms (Spring 2010)/Fingerprinting|Fingerprinting]] | [http://lamda.nju.edu.cn/yinyt/notes/random15.pdf slides] | [http://lamda.nju.edu.cn/yinyt/notes/random15-print.pdf print version]
# Number theory algorithms
# Guest lecture by Yang Yu on ''metaheuristics''. | [http://lamda.nju.edu.cn/yinyt/notes/metaheuristics.pdf slides]
# Distributed Algorithms
# [[Randomized Algorithms (Spring 2010)/Distributed algorithms, data streams|Distributed algorithms, data streams]] |  [http://lamda.nju.edu.cn/yinyt/notes/random17.pdf slides] | [http://lamda.nju.edu.cn/yinyt/notes/random17-print.pdf print version]
# Data streams
# 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 =
= The Probability Theory Toolkit =
* [http://en.wikipedia.org/wiki/Expected_value#Linearity Linearity of expectation] (used in Lecture Notes 1, 3)
* [http://en.wikipedia.org/wiki/Expected_value#Linearity Linearity of expectation] (introduced in Lecture Notes 1, 3)
* [http://en.wikipedia.org/wiki/Independence_(probability_theory)#Independent_events Independent events] and [http://en.wikipedia.org/wiki/Conditional_independence conditional independence] (used in Lecture Notes 1, 3)
* [http://en.wikipedia.org/wiki/Independence_(probability_theory)#Independent_events Independent events] and [http://en.wikipedia.org/wiki/Conditional_independence conditional independence] (introduced in Lecture Notes 3)
* [http://en.wikipedia.org/wiki/Conditional_probability Conditional probability] and [http://en.wikipedia.org/wiki/Conditional_expectation conditional expectation] (used in Lecture Notes 1, 2, 3)
* [http://en.wikipedia.org/wiki/Conditional_probability Conditional probability] and [http://en.wikipedia.org/wiki/Conditional_expectation conditional expectation] (introduced in Lecture Notes 3)
* The [http://en.wikipedia.org/wiki/Law_of_total_probability law of total probability] and the [http://en.wikipedia.org/wiki/Law_of_total_expectation law of total expectation] (used in Lecture Notes 2)
* The [http://en.wikipedia.org/wiki/Law_of_total_probability law of total probability] and the [http://en.wikipedia.org/wiki/Law_of_total_expectation law of total expectation] (introduced in Lecture Notes 2, 3)
* The [http://en.wikipedia.org/wiki/Boole's_inequality union bound] (used in Lecture Notes 3)
* The [http://en.wikipedia.org/wiki/Boole's_inequality union bound] (introduced in Lecture Notes 3)
* [http://en.wikipedia.org/wiki/Bernoulli_trial Bernoulli trials] (used in Lecture Notes 3)
* [http://en.wikipedia.org/wiki/Bernoulli_trial Bernoulli trials] (introduced in Lecture Notes 3)
* [http://en.wikipedia.org/wiki/Geometric_distribution Geometric distribution] (used in Lecture Notes 3)
* [http://en.wikipedia.org/wiki/Geometric_distribution Geometric distribution] (introduced in Lecture Notes 3)
* [http://en.wikipedia.org/wiki/Binomial_distribution Binomial distribution] (used in Lecture Notes 3, 4)
* [http://en.wikipedia.org/wiki/Binomial_distribution Binomial distribution] (introduced in Lecture Notes 3, 4)
* [http://en.wikipedia.org/wiki/Markov's_inequality Markov's inequality] (used in Lecture Notes 4)
* [http://en.wikipedia.org/wiki/Markov's_inequality Markov's inequality] (introduced in Lecture Notes 4)
* [http://en.wikipedia.org/wiki/Chebyshev's_inequality Chebyshev's inequality] (used in Lecture Notes 4)
* [http://en.wikipedia.org/wiki/Chebyshev's_inequality Chebyshev's inequality] (introduced in Lecture Notes 4)
* [http://en.wikipedia.org/wiki/Chernoff_bound Chernoff bound] (used in Lecture Notes 4)
* [http://en.wikipedia.org/wiki/Chernoff_bound Chernoff bound] (introduced in Lecture Notes 4)
* [http://en.wikipedia.org/wiki/Pairwise_independence k-wise independence] (introduced in Lecture Notes 6)
* [http://en.wikipedia.org/wiki/Martingale_(probability_theory) Martingale] (introduced in Lecture Notes 7)
* [http://en.wikipedia.org/wiki/Azuma's_inequality Azuma's inequality] and [http://en.wikipedia.org/wiki/Hoeffding's_inequality Hoeffding's inequality] (introduced in Lecture Notes 7)
* [http://en.wikipedia.org/wiki/Doob_martingale Doob martingale] (introduced in Lecture Notes 7)
* The [http://en.wikipedia.org/wiki/Probabilistic_method  probabilistic method] (introduced in Lecture Notes 8)
* The [http://en.wikipedia.org/wiki/Lov%C3%A1sz_local_lemma  Lovász local lemma]  and the [http://en.wikipedia.org/wiki/Algorithmic_Lov%C3%A1sz_local_lemma algorithmic Lovász local lemma] (introduced in Lecture Notes 8)
* [http://en.wikipedia.org/wiki/Markov_chain Markov chain]:
::[http://en.wikipedia.org/wiki/Markov_chain#Reducibility reducibility], [http://en.wikipedia.org/wiki/Markov_chain#Periodicity Periodicity], [http://en.wikipedia.org/wiki/Markov_chain#Steady-state_analysis_and_limiting_distributions stationary distribution], [http://en.wikipedia.org/wiki/Hitting_time hitting time], cover time, (introduced in Lecture Notes 10);
::[http://en.wikipedia.org/wiki/Markov_chain_mixing_time mixing time], [http://en.wikipedia.org/wiki/Conductance_(probability) conductance] (introduced in Lecture Notes 11 and 12)


= Acknowledgment =
= Acknowledgment =
Thanks the [http://lamda.nju.edu.cn/ LAMDA group] for hosting the webpage for off-campus users. Special thanks to [http://lamda.nju.edu.cn/yuy YU Yang] for his time and technical supports.
Thanks the [http://lamda.nju.edu.cn/ LAMDA group] for hosting the webpage for off-campus users. Special thanks to [http://lamda.nju.edu.cn/yuy YU Yang] for his time and technical supports.

Latest revision as of 03:37, 18 July 2011

随机算法 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.
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中有一处笔误，[math]\displaystyle{ \epsilon }[/math]应为[math]\displaystyle{ \epsilon^2 }[/math]。感谢钱超同学发现这个问题。
(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

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

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

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

先修课程 Prerequisites

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

Course materials

Policies

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.

Retrieved from "https://tcs.nju.edu.cn/wiki/index.php?title=Randomized_Algorithms_(Spring_2010)&oldid=478"