|
| 1.
| [Abstract Concepts]
Understand abstract mathematical concepts which are involved in designing advanced algorithms, e.g., probability theory, conditional expectation, Markov's inequality, measure concentration.
|
| 2.
| [Problem Solving]
Be able to apply abstract concepts in designing sophisticated algorithms to tackle various problems, e.g., MAX-CUT, MAX-3-SAT, Set Cover, PAC-learning. |
| 3.
| [Performance Analysis]
Be able to apply formal reasoning to analyze the performance of algorithms, e.g., in terms of running time, space, failure probability, number of random bits, number of samples. |
| 4.
| [Independent and Lifelong Learning]
Be inspired to learn independently and motivated to solve challenging problems.
|
Mapping from Course Learning Outcomes to Programme Learning Outcomes
| | PLO a | PLO b | PLO c | PLO d | PLO e | PLO f | PLO g | PLO h | PLO i | PLO j |
| CLO 1 | T | | T | | | | | | | |
| CLO 2 | T | T | T | | | | | | | T |
| CLO 3 | T | | T | | | | | | | T |
| CLO 4 | T | | | | | | | | T | T |
T - Teach, P - Practice
For BEng(CompSc) Programme Learning Outcomes, please refer to
here.
|
| Syllabus |
|
Calendar Entry:
This class introduces advanced mathematical techniques for analyzing the complexity and correctness of algorithms. 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.
|
|
Detailed Description:
| Basic Probability Theory |
Mapped to CLOs
|
| Markov's Inequality, Chebyshev's Inequality | 1 |
| Probabilistic method: MAX-CUT, MAX-3SAT | 1, 2 |
| Conditional Expectation | 1, 3 |
| Measure Concentration |
Mapped to CLOs
|
| Method of Moment Generating Function | 1, 2 |
| Chernoff Bound, Hoeffding's Inequality | 1, 3 |
| Advanced Topics |
Mapped to CLOs
|
| Johnson-Lindenstrauss Lemma | 2, 3, 4 |
| Epsilon-nets, Epsilon-cover and PAC | 2, 3, 4 |
| Lovasz Local Lemma and Job Shop Scheduling | 2, 3, 4 |
|
|
Assessment:
Written Examination:
50%
Continuous Assessment:
50%
|
| Teaching Plan |
|
Please refer to the corresponding Moodle course.
|
| Moodle Course(s) |
|
|
