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
Syllabus

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.

Topics
Pre-requisites  
Compatibility  
Instructor's web  
Assessment
  • In-course assessment:
  • Examination marks:
Timetable

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 -