Courses Offered

COMP3250 Design and Analysis of Algorithms

2021-22

Instructor(s):

Lam T W

(Class A)

No. of credit(s):

Huang Z.Y.

(Class B)

Recommended Learning Hours:

Lecture:

39.0

Pre-requisite(s):

COMP2119

Co-requisite(s):

Mutually exclusive with:

Remarks:

For COMP3250-1A (Advanced Class), students who have obtained a B grade or higher in COMP2119 are eligible for taking the advanced class and their enrollment will be accepted automatically; other students need to seek the approval of the lecturer, Professor TW Lam by email (twlam@cs.hku.hk) or face-to-face (CB 301).

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.	[Program 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 a	PLO c
CLO 1	T,P
CLO 2	T,P
CLO 3	T,P	T,P
CLO 4	T,P	T,P
CLO 5		T,P

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

Syllabus

Calendar Entry:
The course studies various algorithm design techniques, such as divide and conquer, and dynamic programming. These techniques are applied to design novel algorithms from various areas of computer science. Topics include: advanced data structures; graph algorithms; searching algorithms; gemometric algorithms; overview of NP-complete problems.

Detailed Description:

Basic algorithm design technique	Mapped to CLOs
Divide and Conquer	1, 3, 5
Greedy algorithms	1, 3, 5
Graph algorithms	1, 3, 5
Advanced algorithm design technique	Mapped to CLOs
Dynamic programming	2, 3, 5
Network flow	2, 3, 5
Intractability	Mapped to CLOs
Problem reduction and NP-completeness	2, 3, 4, 5
Approximation Algorithms	3, 4, 5

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

Teaching Plan

Please refer to the corresponding Moodle course.

Moodle Course(s)

Courses Offered

COMP3250 Design and Analysis of Algorithms

Sign in to your account

Sign in to your account