The School of Computing and Data Science (https://www.cds.hku.hk/) was established by the University of Hong Kong on 1 July 2024, comprising the Department of Computer Science and Department of Statistics and Actuarial Science.

Courses Offered

COMP3252 Algorithm design and analysis

COMP3252 Algorithm design and analysis

2024-25
Instructor(s):Lam T W
(Class A) No. of credit(s):6
Recommended Learning Hours:
Lecture: 39.0
Pre-requisite(s):COMP2119
Co-requisite(s):  
Mutually exclusive with:COMP3250 or COMP3251
Remarks:Pre-requisite COMP2119 (Grade B or above) or special approval by instructor

Course Learning Outcomes

1. [Basic algorithm design technique]
Understand basic techniques for designing algorithms, including the techniques of recursion, divide-and-conquer, and greedy.
2. [Advanced algorithm design technique]
Understand advanced techniques for designing algorithms, including dynamic programming, network flow and problem reduction.
3. [Correctness and time complexity]
Understand the techniques of proof by contradiction, mathematical induction and recurrence relation, and apply them to prove the correctness and to analyze the running time of algorithms.
4. [Intractability]
Understand the mathematical criterion for deciding whether an algorithm is efficient, and know many practically important problems that do not admit any efficient algorithms.
5. [Problem solving]
Able to apply the algorithm design techniques to design efficient algorithms for different kinds of problems
Mapping from Course Learning Outcomes to Programme Learning Outcomes
 PLO aPLO bPLO cPLO dPLO ePLO fPLO gPLO hPLO iPLO j
CLO 1T,P
CLO 2T,P
CLO 3T,PT,P
CLO 4T,PT,P
CLO 5T,P

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

Syllabus

Calendar Entry:
The course studies principles of algorithm design and the analysis of sophisticated algorithms (regarding proof of correctness and time complexity). Topics include divide-and-conquer, dynamic programming, greedy algorithms, graph algorithms, network flow, geometric algorithms, and NP-completeness. The course puts emphasis on mathematical rigor; it expects students to figure out the mathematics and logic that make algorithms work. Students can form pairs to discuss the assignments and are required to write rigorous proofs of correctness and analysis independently.

Detailed Description:

Basic algorithm design technique Mapped to CLOs
Divide and Conquer1, 3, 5
Greedy algorithms1, 3, 5
Graph algorithms1, 3, 5
Advanced algorithm design technique Mapped to CLOs
Dynamic programming2, 3, 5
Network flow2, 3, 5
Intractability Mapped to CLOs
Problem reduction and NP-completeness2, 3, 4, 5
Approximation Algorithms3, 4, 5

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

Teaching Plan

Please refer to the corresponding Moodle course.

Moodle Course(s)

Don't have an account yet? Register Now!

Sign in to your account

Don't have an account yet? Register Now!

Sign in to your account