Announcement
- Nov 26. If you have any questions about the grading of assignments or quiz, please resolve them on or before Dec 13.
- Sep 20. Homework 2 is released here. The due date is Oct 14.
- Sep 9. Please hand in your homework in assignment box L3.
- Sep 2. Welcome to the class! Homework 1 is out and due Sep 16. The assignment box number for the class will be announced later.
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.
Previous Class: This class was previously taught in year 2009.
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
- Lovasz Local Lemma
- Job Shop Scheduling
- Other Advanced Topics
Textbook
There is no compulsory text, but here are some suggested
textbooks:
Newsgroup
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.
Assessment
- 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.
Plagiarism
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.
Lecture notes will be posted as soon as they are available.
- 2 Sep. Course info, basics of probability, probabilistic method.
- Slides. (Course admin, Probability basics)
- Notes 1. (Probabilistic Method, Markov's Inequality, Chebyshev's Inequality)
- 6 Sep. Continue with Probabilistic Method.
- 7 Sep. Tutorial - Probability Review
- Basic Probability
- Random Variables
- These are some introductory slides. Please review them and send email to Mingfei about which particular probability concepts you would like us to cover during the tutorial.
- 9 Sep. Derandomization by Conditional Expectation, Graphs with No Short Cycles (Method of Alteration)
- 13 Sep. Continue with Notes 2.
- 16 Sep. Set Cover: Randomized Rounding
- 20 Sep. Set Cover: Greedy Algorithm
- 27 Sep. Group Tutorial
- 30 Sep. Chernoff Bound, Measure Concentration
- 4 Oct. More Measure Concentration: Counting DNF Satisfying Assignments, Hoeffding's Inequality.
- 7 Oct. Continue with Hoeffding's Inequality.
- 11 Oct. Johnson-Lindenstrauss Lemma: Dimension Reduction
- 11 Oct. Continue with Johnson-Lindenstrauss Lemma
- 25 Oct. Revision: Estimating (Unknown) Fraction of Red Balls
- 1 Nov. Midterm Review
- 4 Nov. epsilon-Nets, VC-Dimension
- 8 Nov. epsilon-Nets, epsilon-Samples, VC-Dimension (Part 2)
- 11 Nov. Continue with epsilon-Nets, epsilon-Samples, VC-Dimension
- 15 Nov. Lovasz Local Lemma, Job Shop Scheduling.
- 18 Nov. Continue with Lovasz Local Lemma, Job Shop Scheduling.
- 22 Nov. Continue with Job Shop Scheduling, Dominating Random Variables.
- 25 Nov. Lovasz Local Lemma (Part 2): Asymptotically Optimal Job Shop Scheduling
- 29 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.
- Homework 1, due 16 Sep.
- Homework 2, due 14 Oct.
(In HW 2, Question 1, you may assume the stronger condition n >= 2^{l+2}.)
- Homeworks 3+4, due 29 Nov.