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.0
Tutorial: 3.0
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)

Please login with your CS account (for staff only)