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:  Monte Carlo Method, Mixing, 

                  Martingales, Balanced Allocations



六、成績考核 (Evaluation) 



    5 Assignments:  Best four     * 37% (@ 9.25%)

                    Remaining one *  3%



    Midterm Quiz:                   10%

    Final Exam:                     50%

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

    Total                          100%



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

    06年下學期之網頁 [連結]