Randomized Algorithms (Spring 2010): Difference between revisions
Jump to navigation
Jump to search
imported>WikiSysop |
imported>WikiSysop |
||
Line 95: | Line 95: | ||
= Probability Toolkit = | = Probability Toolkit = | ||
* [http://en.wikipedia.org/wiki/Expected_value#Linearity Linearity of expectation] | * [http://en.wikipedia.org/wiki/Expected_value#Linearity Linearity of expectation] | ||
* [http://en.wikipedia.org/wiki/Independence_(probability_theory)#Independent_events Independent events] | |||
* [http://en.wikipedia.org/wiki/Conditional_probability Conditional probability] and [http://en.wikipedia.org/wiki/Conditional_expectation conditional expectation] | * [http://en.wikipedia.org/wiki/Conditional_probability Conditional probability] and [http://en.wikipedia.org/wiki/Conditional_expectation conditional expectation] | ||
* 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 | * 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] | ||
Revision as of 06:59, 10 January 2010
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/random2010/
Announcement
There is no announcement yet.
Syllabus
随机化(randomization)是现代计算机科学最重要的思想方法之一,近二十年来被广泛的应用于计算机科学的各个领域。在这些应用的背后,是一些共通的随机化原理。在随机算法这门课程中,我们将用数学的语言描述这些原理,将会介绍以下内容:
- 一些重要的随机算法的设计与分析;
- 概率论工具,包括常用的概率不等式,以及数学证明的概率方法 (the probabilistic method);
- 随机算法的概率模型,包括典型的随机算法模型,以及概率复杂度模型。
作为一门理论课程,这门课的内容偏重数学上的分析和证明。这么做的目的不单纯是为了追求严格性,而是因为用更聪明的方法去解决问题往往需要对问题本身的数学结构有深刻的认识。
先修课程 Prerequisites
必须:离散数学,概率论。 推荐:算法设计与分析。
教材和参考书 Course materials
规则 Policies
Assignments
There is no assignment yet.
Lecture Notes
- Introduction
- Complexity classes, lower bounds
- Expectations, moments, deviations
- Probabilistic inequalities
- Hashing, limited independence
- 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 streaming