title: 隨機演算法 (Randomized Algorithms)

課程大綱：

一、課程說明 (Course Description)

The following is modified from Preface of our textbook:

Randomization and probabilistic techniques play an important role in modern

computer science, with applications ranging from combinatorial optimization

and machine learning to communication networks and secure protocols. This

course intends to give an introduction to the probabilistic techniques and

paradigms used in the development of probabilistic algorithms and analyses.

Only elementary background in **discrete mathematics** is required.

二、指定用書 (Text Book)

**Probability and Computing:** Randomized Algorithms and

Probabilistic Analysis, by Michael Mitzenmacher and Eli Upfal

三、參考書籍 (References)

1. Randomized Algorithms, by Rajeev Motwani and Prabhakar Raghavan

2. The Probabilistic Method by Noga Alon and Joel Spencer

四、教學方式 (Teaching Method)

Lectures and Tutorials (Lectures in **English**)

五、教學進度 (Syllabus)

Basic Topics: Events and Probability,

Discrete Random Variables and Expectation,

Moments and Deviations

Core Topics: Chernoff Bounds, Random Graphs,

Markov Chain and Random Walks

Advanced Topics: Mixing, Balanced Allocations (if time is available)

六、成績考核 (Evaluation)

5 Assignments: 0%

3 Exams: 100%

---------------------

Total 100%

There are two formulas, and we will choose whichever gives you the higher score:

Formula 1: ( Average of Best 2 Exams ) * 0.8 + ( Remaining Exam ) * 0.2

Formula 2: 30% + ( Average of 3 Exams ) * 0.7

七、可連結之綱址 (Web links)

12年之網頁 [http://www.cs.nthu.edu.tw/~wkhon/random12.html">]