|
Materials on this website are for educational use only. Do not distribute copyrighted materials. 這是為2006年秋季
【機率方法】課程所設的網頁。在上課的場次
The purpose of this course is to introduce probabilistic methods in Combinatorics and their applications in theoretical Computer Science. This is a research oriented course. I will be trying to use material both from combinatorics and algorithms, but the emphasis will be on combinatorics. The topics include linearity of expectation, the second moment method, the local lemma, correlation inequalities, martingales, large deviation inequalities, geometry, derandomization (changes are possible).
Textbook: (1) The Probabilistic Method, 2nd Ed, by Noga Alon and Joel Spencer, 2000. (Primary Textbook) (2) Graph Colouring and the Probabilistic Method, by Molloy M and Reed B.,Springer-Verlag, 2001. (3) Randomized Algorithms, by Motwani and Raghavan, 1995. (4) Probability and Computing, by Mitzenmacher and Upfal, 2005. (5) Finite Markov Chains and Algorithmic Applications, by Olle Häggström , 2002.
Grading Policy: 期中考 35%（11月22日）、期末考 35%（1月17日）、short report 20%、class performance 10%。
完成短報告的方法有兩種，你可在下列可做為報告題材的論文中，選一篇來讀，並將文章中最重要的結果之詳細證明寫成短報告。你也可在下列可做為報告題材的問題中，選一來解，並將證明結果寫成短報告。
|
|
