Courses Offered

COMP3351 Advanced Algorithm Analysis

COMP3351 Advanced Algorithm Analysis

2020-21
Instructor(s):Huang Z.Y.
(Class A) No. of credit(s):6
Recommended Learning Hours:
 Lecture: 36 Tutorial: 3
Pre-requisite(s):COMP3250
Co-requisite(s):
Mutually exclusive with:
Remarks:

Course Learning Outcomes

 1 [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 [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 [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 [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 aPLO bPLO cPLO dPLO ePLO fPLO gPLO hPLO iPLO j
CLO 1TT
CLO 2TTTTT
CLO 3TTTTT
CLO 4T

T - Teach, P - Practice
For BEng(CompSc) Programme Learning Outcomes, please refer to here.

Syllabus

Calendar Entry:

Detailed Description:

Basic Probability Theory Mapped to CLOs
Markov’s Inequality, Chebyshev’s Inequality1
Probabilistic method: MAX-CUT, MAX-3SAT1, 2
Conditional Expectation1, 3
Measure Concentration Mapped to CLOs
Method of Moment Generating Function1, 2
Chernoff Bound, Hoeffding’s Inequality1, 3
Advanced Topics Mapped to CLOs
Johnson-Lindenstrauss Lemma2, 3, 4
Epsilon-nets, Epsilon-cover and PAC2, 3, 4
Lovasz Local Lemma and Job Shop Scheduling2, 3, 4

Assessment:
Continuous Assessment: 50%
Written Examination: 50%

Teaching Plan

Please refer to the corresponding Moodle course.

Moodle Course(s)