Courses Offered

COMP3351 Advanced Algorithm Analysis

2020-21

Instructor(s):

Huang Z.Y.

(Class A)

No. of credit(s):

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.

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 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:
Continuous Assessment: 50%
Written Examination: 50%

Teaching Plan

Please refer to the corresponding Moodle course.

Moodle Course(s)