Course Aims & Objectives:
This course aims to provide a comprehensive introduction to algorithm design and analysis.
Upon completion, students should be able to:

1. apply algorithm design techniques to problem solving;
2. analyse the complexities of algorithms.

Units: 3

Level: B3

Medium of Instruction: English

Keyword Syllabus:
Algorithm complexities: upper bounds and lower bounds. Recurrence relations. Concepts on NP, basic methods to prove the NP-completeness of a problem. Concepts and algorithms in computational geometry. Algorithms for some common graph problems: shortest path, minimum spanning tree, connectivity and transitive closure . String algorithms.

Teaching Pattern:
Duration of course: 1 semester
Current mix of lecture/tutorial/laboratory, other: 2 hrs. lecture; 1 hr. tutorial.

Assessment Pattern:
Examination duration: 2 hours
Percentage distribution of marks for coursework, examination, other: 30% CW; 70% Exam
Grading pattern: Standard (A+AA-...F)
For a student to pass the course, at least 30% of the maximum mark for the examination must be obtained.

Pre-requisite(s):
CS2302 /or
both CS2468 and MA2504 /or equivalent

Pre-cursor(s): Nil

Equivalent Course(s):
*CS3371 Design and Analysis of Algorithms