IP4003 - Complexity

IP4003 - Complexity

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.

Hours

  • Lectures : 11
This course is part of the programme

In brief

ECTS credits : cf Teaching Unit

Number of hours 11

Contact(s)

Nicolas BARNIER

Phone : +33 5 62 25 95 06

Email : nicolas.barnier @ enac.fr

Jean-Baptiste GOTTELAND

Phone : +33 5 62 25 95 84

Email : jean-baptiste.gotteland @ enac.fr