Algorithm Design and Analysis

Synopsis

ICT325 aims to develop knowledge, understanding and skills about algorithm design and analysis, which is fundamental to all areas of computer science. This course provides an introduction to various algorithms through common algorithm design paradigms, including sorting, optimal sequencing, string matching, greedy optimisation, divide and conquer, dynamic programming, recursive algorithms, etc. This course will also illustrate the concepts of complexity classes P and NP as well as greedy heuristic approach for solving NP-complete problems.

Level: 3
Credit Units: 5
Presentation Pattern: EVERY JULY

Topics

Introduction to Algorithms
Complexity analysis with Big-O Notation
Brute-force sorting advanced
Brute-force combinatorics: backtracking, branch and bound and generating permutations
Divide and Conquer: sort, partitioning, and search
Divide and Conquer: closest pair and convex hull
Dynamic Programming Basics
Dynamic Programming Advance
Greedy Algorithms
Graph algorithms
Analysis Techniques
Introduction to NP Completeness

Learning Outcome

Describe difference and advantages of iterative and recursive algorithms
Demonstrate the correctness of algorithms
Apply various existing algorithms to real world use cases
Discuss speed and space trade-off, importance of data-structures, and data preprocessing
Design new algorithms using the learned knowledge
Implement heuristic approach to demonstrate NP hard problem

Part-time Programmes / CET Courses

Singapore University of Social Sciences

Algorithm Design and Analysis