COMP8603 - Probabilistic Method and Randomized Algorithms
Semester 1, 2017-18
This is a Graduate Course. MPhil/PhD students in the Department of Computer Science should read the Coursework Requirement.
Instructor Dr HTH Chan

This course is designed for students who have a basic knowledge in algorithms and would like to study more advanced topics in the subject. NP-complete problems are believed to be not solvable in polynomial time and we study how approximation algorithms could give near optimal solutions. In particular, we will see that probability theory gives us a very powerful tool to tackle problems that are otherwise hard to solve. The surprising phenomenon that independent random sources can give rise to almost certain events is known as measure concentration, and this principle forms the basis of the analysis of many randomized algorithms. This course is taught in the style of a mathematics class and we put emphasis on understanding how the various techniques work. However, we explain the subject from the computer scientist’s viewpoint - our approach is rigorous, but not pedantic.

Instructor's web  
  • In-course assessment:
  • Examination marks:

Teaching Period: September 1, 2017 - November 30, 2017
Reading Week: October 16, 2017 - October 21, 2017

Date Start Time End Time Venue Remark
Wednesday 2:30pm 5:30pm JLG03

G/F James Hsioung Lee Science Building

Discussion board  

- End -