Randomized Algorithms (Spring 2010) and Main Page: Difference between pages

From TCS Wiki
(Difference between pages)
Jump to navigation Jump to search
VisualWikitext
imported>WikiSysop
 
imported>WikiSysop
mNo edit summary
 
Line 1: Line 1:
{{Infobox
<big>'''MediaWiki has been successfully installed.'''</big>
|name        = Infobox
|bodystyle    =
|title        = 随机算法
Randomized Algorithms
|titlestyle  =


|image        = [[File:MR-randomized-algorithms.png|100px]]
随机算法
|imagestyle  =
|caption      = ''Randomized Algorithms'' by Motwani and Raghavan
|captionstyle =
|headerstyle  = background:#ccf;
|labelstyle  = background:#ddf;
|datastyle    =


|header1 =Instructor
Consult the [http://meta.wikimedia.org/wiki/Help:Contents User's Guide] for information on using the wiki software.
|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;
== Getting started ==
|below =
* [http://www.mediawiki.org/wiki/Manual:Configuration_settings Configuration settings list]
}}
* [http://www.mediawiki.org/wiki/Manual:FAQ MediaWiki FAQ]
 
* [https://lists.wikimedia.org/mailman/listinfo/mediawiki-announce MediaWiki release mailing list]
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 =
* (04/05/2010) <font size ="5" color="red">第六课的slides已上传。</font>
* (04/03/2010) <font size ="5" color="red">第一次作业答案已公布。</font>
* (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 =
* (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/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]]
# The probabilistic method
# Randomized rounding
# Random graphs, graph algorithms
# Markov chains and random walks
# Random sampling
# Approximate counting
# Geometric 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.

Revision as of 06:09, 24 December 2009

MediaWiki has been successfully installed.

随机算法

Consult the User's Guide for information on using the wiki software.

Getting started

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