CSIS0351 Advanced Algorithm Analysis/CSIS8601 Advanced Topics in Theoretical Computer Science, Fall 2011

Time and Place:
Mon: 05:00PM - 05:55PM Meng Wah Complex Theatre 4
Thu: 03:00PM - 04:55PM Rayson Huang Theatre (except Sep 29)

Instructor: Hubert Chan
Consultation Hours (1 to 1): Thu 5-7pm CYC 429
(Please send email in advance if you come after 6pm.)

Mingfei Li (mfli at cs.hku.hk)
Consultation Hours: Mon 7-8pm CYC LG101

Fei Chen (fchen at cs.hku.hk)
Consultation Hours: Tue 5-6pm CYC LG101

Arrange as needed. (No consultation hours when there is tutorial.)
Next Tutorial: Sep 20 (Tue), 6pm CYC 308


  • Dec 8. HW 3+4 has been graded. You may collect them from Fei Chen at CYC LG101.
  • Nov 13. The notes on the limitation of blackbox sampling and Pollard's Kangaroo Algorithm are available.
  • Oct 31. HW 3+4 is released and due Nov 28.
  • Oct 24. Both TAs have moved their offices to CYC LG101. You may also collect the graded HW 1 and 2 from them.
  • Sep 30. The mid-term will be held on Oct 27. More information is here.
  • Sep 26. Special arrangement: the class will be held in K419 (Knowles Bldg) on Sep 29.
  • Sep 22. HW2 is released and due Oct 10.
  • Sep 18. The next tutorial is on Sep 20 (Tue) at 6pm CYC 308. Consultation hours on Mon Sep 19 will be held by Hubert right after class.
  • Sep 15. Please hand in your solution in the assignment box L3 at the corner of the 3rd-floor lobby in CYC Building. In other words, do not put your solution in a box if you do not see "L3" on it.
  • Sep 8. Because of Mid-Autumn Festival, there will be no consultation hours or tutorials on Sep 12 and 13. Lecture on Mon Sep 12 will be as usual at 5pm.
  • Sep 1. There will be a tutorial on basic probability on Mon Sep 5, 7PM CYC 308.
  • Sep 1. HW1 is released and due Sep 19.

Course Information

Course Material


Course Information

This class 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.

Prerequisites: Students should have a basic knowledge of probability and algorithms. For example, probability space, discrete and continuous random variables, expectation, independence, probability density function, normal (Gaussian) distribution. However, we would also recall the necessary concepts as the course proceeds. Students from all faculties are welcome to take this class; please email the instructor if you need help to register the class.

Previous Class: This class was previously taught in years 2009 and 2010.

Topics Covered

  • Basic Probability Theory
  • Probabilistic Method
  • Randomized Algorithms, Conditional Expectation
  • Measure Concentration, Method of Moment Generating Function
  • Chernoff Bound, Hoeffding Inequality
  • Dimension Reduction (Johnson-Lindenstrauss Lemma)
  • epsilon-nets, VC-dimension
  • VC-dimension and PAC learning
  • Other Advanced Topics


There is no compulsory text, but here are some suggested textbooks:


If you have questions concerning the class, sending us an email is the quickest way to get our attention. However, if you would like to post a public comment or suggestion, you can do so using the newsgroup.


  • 3-4 homeworks (25%)
  • 1 or 2 quizzes (25%)
  • Final examination (50%)

Late Homework Policy:
1 Day late: 50% credit, 0% credit after
If you have special reasons for handing in your homework late, please let us know in advance.


You are allowed and encouraged to discuss the homework with other students and the tutors. However, you have to write up the answers alone (i.e., you are not allowed to see the writeup of another student) and declare the names of the people with whom you have discussed.
As defined in the University's Regulations Governing Conduct at Examinations, plagiarism is the unacknowledged use, as one's own, of work of another person, whether or not such work has been published. Or put it simply, plagiarism is copying the work of another person without proper acknowledgement. In case of queries on plagiarism, students are strongly advised to refer to "What is Plagiarism?".

First Attempt:
Students who admit committing plagiarism for the first time shall be warned in writing and receive a zero mark for the component concerned. For those who do not confess, the case would be referred to the Programme Director for consideration.
Subsequent Attempt:
If students commit plagiarism more than once during the course of studies, the case shall be referred to the Programme Director for consideration. The Programme Director will investigate the case and consider referring it to the University Disciplinary Committee, which may impose any of the following penalties: a published reprimand, suspension of study for a period of time, fine, or expulsion from the University.

Course Material

Lecture notes will be posted as soon as they are available.
  1. 1 Sep. Course info, basics of probability, probabilistic method.
    • Slides. (Course admin, Probability basics)
    • Notes 1. (Probabilistic Method, Markov's Inequality, Chebyshev's Inequality)
  2. 5 Sep. Lecture at 5pm (Meng Wah Complex Theatre 4), Tutorial at 7pm (CYC 308) - Probability Review
  3. 8 Sep. Derandomization by Conditional Expectation, Graphs with No Short Cycles (Method of Alteration)
  4. 12 Sep. More on Derandomization (using Pairwise Independence)
  5. 15 Sep. Set Cover: Randomized Rounding
  6. 19 Sep. Chernoff Bound, Measure Concentration
  7. 22 Sep. More Measure Concentration: Counting DNF Satisfying Assignments, Hoeffding's Inequality.
  8. 26 Sep. Counting DNF Satisfying Assignments
  9. 29 Sep. Class cancelled due to Typhoon.
  10. 3 Oct. Continue with Hoeffding's Inequality.
  11. 6 Oct. More Examples for Measure Concentration. (1) Impossibility Result to Achieve Multiplicative Error for Blackbox Sampling. (2) Pollard's Kangaroo Algorithm
  12. 10 Oct. Johnson-Lindenstrauss Lemma: Dimension Reduction
  13. 13 Oct. Proof of Johnson-Lindenstrauss Lemma
  14. 24 Oct. Revision
  15. 27 Oct. Mid-term Exam.
  16. 31 Oct. epsilon-Nets, VC-Dimension
  17. 3 Nov. Continue with epsilon-Nets, VC-Dimension
  18. 7 Nov. epsilon-Nets, epsilon-Samples, VC-Dimension (Part 2)
  19. 10 Nov. Continue with epsilon-Nets, epsilon-Samples, VC-Dimension
  20. 14 Nov. Differential Privacy, Laplace Distribution
  21. 17 Nov. Differential Privacy (Continue)
  22. 21 Nov. Private Continual Release of Statistics
  23. 24 Nov. Private Continual Release of Statistics (Cont'd)
  24. 28 Nov. Exam Review.


Please put the solution to your homework in the assignment box L3 at the corner of the 3rd-floor lobby in CYC Building on or before the due date at 9pm.
If you have special reasons for handing in your homework late, please let us know in advance.
  1. Homework 1, due 19 Sep.
  2. Homework 2, due 10 Oct.
  3. Homeworks 3+4, due 28 Nov.