imported>WikiSysop |
imported>WikiSysop |
| Line 1: |
Line 1: |
| {{Infobox
| | This is a wiki run by Yitong Yin (尹一通), Nanjing University. |
| |name = Infobox
| |
| |bodystyle =
| |
| |title = 随机算法
| |
| Randomized Algorithms
| |
| |titlestyle =
| |
|
| |
|
| |image = [[File:MR-randomized-algorithms.png|100px]]
| | == Courses Home Pages == |
| |imagestyle =
| | ; Computer Science |
| |caption = ''Randomized Algorithms'' by Motwani and Raghavan
| | * [[Combinatorics (Fall 2010)|组合数学 Combinatorics, Fall 2010.]] |
| |captionstyle =
| |
| |headerstyle = background:#ccf;
| |
| |labelstyle = background:#ddf; | |
| |datastyle =
| |
|
| |
|
| |header1 =Instructor | | * [[Randomized Algorithms (Spring 2010)|随机算法 Randomized Algorithms, Spring 2010.]] |
| |label1 =
| |
| |data1 =
| |
| |header2 =
| |
| |label2 =
| |
| |data2 = 尹一通
| |
| |header3 =
| |
| |label3 = Email
| |
| |data3 = yitong.yin@gmail.com yinyt@nju.edu.cn yinyt@lamda.nju.edu.cn
| |
| |header4 =
| |
| |label4= office
| |
| |data4= 蒙民伟楼 406
| |
| |header5 = Class
| |
| |label5 =
| |
| |data5 =
| |
| |header6 =
| |
| |label6 = Class meetings
| |
| |data6 = 10 am-12 am, Tuesday, <br><font color="red" size="3">馆III-101</font>
| |
| |header7 =
| |
| |label7 = Place
| |
| |data7 =
| |
| |header8 =
| |
| |label8 = Office hours
| |
| |data8 = 2pm-5pm, Saturday, MMW 406
| |
| |header9 = Textbook
| |
| |label9 =
| |
| |data9 =
| |
| |header10 =
| |
| |label10 =
| |
| |data10 = Motwani and Raghavan, ''Randomized Algorithms''. Cambridge Univ Press, 1995.
| |
|
| |
|
| |belowstyle = background:#ddf;
| | ; Atmospheric Sciences |
| |below =
| |
| }}
| |
|
| |
|
| 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.
| | * [[大气环流(Fall 2010)|大气环流 General Circulation of the Atmosphere, Fall 2010]] |
|
| |
|
| There is also a backup page for off-campus users. The URL is http://lamda.nju.edu.cn/yinyt/random2010wiki/
| | == Personal Home Pages == |
| | * [http://lamda.nju.edu.cn/yinyt/ Yitong Yin's Homepage] |
|
| |
|
| = Announcement = | | == Acknowledgment == |
| * (04/22/2010) 由于老师外出，本周officie hour取消。
| |
| * (04/21/2010) <font size ="5" color="red">第二次作业答案已公布。</font>
| |
| * (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 ===
| |
| * [[Randomized Algorithms (Spring 2010)/Course materials|教材和参考书清单]]
| |
| | |
| === Policies ===
| |
| * [[Randomized Algorithms (Spring 2010)/Policies|Policies]]
| |
| | |
| = Assignments =
| |
| * (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/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 =
| |
| # [[Randomized Algorithms (Spring 2010)/Introduction|Introduction]] | [http://lamda.nju.edu.cn/yinyt/notes/random1.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]
| |
| # [[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)/More on Chernoff bounds| Set balancing, packet routing, and metric embedding]] | [http://lamda.nju.edu.cn/yinyt/notes/random5.pdf slides] | [http://lamda.nju.edu.cn/yinyt/notes/random5-print.pdf print version]
| |
| # [[Randomized Algorithms (Spring 2010)/Hashing, limited independence | Hashing, limited independence]] | [http://lamda.nju.edu.cn/yinyt/notes/random6.pdf slides] | [http://lamda.nju.edu.cn/yinyt/notes/random6-print.pdf print version]
| |
| # [[Randomized Algorithms (Spring 2010)/Martingales | Martingales]] | [http://lamda.nju.edu.cn/yinyt/notes/random7.pdf slides] | [http://lamda.nju.edu.cn/yinyt/notes/random7-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>
| |
| # [[Randomized Algorithms (Spring 2010)/Markov chains and random walks | Markov chains and random walks]]
| |
| # Random sampling
| |
| # Approximate counting
| |
| # Geometric algorithms and linear programming
| |
| # Random graphs, graph algorithms
| |
| # Fingerprinting
| |
| # Number theory algorithms
| |
| # Distributed Algorithms
| |
| # Data streams
| |
| | |
| = 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/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/Conditional_probability Conditional probability] and [http://en.wikipedia.org/wiki/Conditional_expectation conditional expectation] (used in Lecture Notes 1, 2, 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/Boole's_inequality union bound] (used in Lecture Notes 3)
| |
| * [http://en.wikipedia.org/wiki/Bernoulli_trial Bernoulli trials] (used in Lecture Notes 3)
| |
| * [http://en.wikipedia.org/wiki/Geometric_distribution Geometric distribution] (used in Lecture Notes 3)
| |
| * [http://en.wikipedia.org/wiki/Binomial_distribution Binomial distribution] (used 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/Chebyshev's_inequality Chebyshev's inequality] (used in Lecture Notes 4)
| |
| * [http://en.wikipedia.org/wiki/Chernoff_bound Chernoff bound] (used in Lecture Notes 4)
| |
| | |
| = 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. |