Singapore University of Social Sciences

Algorithm Design and Analysis

Algorithm Design and Analysis (ICT325)

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
Back to top
Back to top