IP4003 - Complexity of algorithms

Objectives

General objective:

Be able to compute time and space complexities of sequential algorithms.
Be able to apply the technique of dynamic programming to optimize recursive formulations.
Be able to compare algorithms and choose the most suitable.

Detailed objectives:

Master the notions of worst-case time and space complexities of sequential algorithms.
Be able to compute and compare asymptotic complexity expressions of iterative and recursive algorithms.
Be able to transform some recursive algorithms into iterative ones with dynamic programming.
Understand the notion of optimal complexity.
Know the problem classes NP, P, NPC and NP-Hard.
Be able to compare algorithms and choose the most suitable to solve a given problem depending on the
context.