Algorithms Design and Complexity
- Enseignant(s)
- Ikko YAMANE
- Course type
- COMPUTER SCIENCE
- Unit
-
Module UE1-03-M-E-S : Data Bases and Fundamentals of Computer Science
- Number of ECTS
- 2
- Course code
- 1AINF04
- Distribution of courses
-
Heures de cours : 9
Heures de TP : 12
- Language of teaching
- French
- Modalités d'évaluation
- examen écrit de 2h sans document
Objectifs
Calculate the complexity of an algorithm and estimate the time needed to complete it
Produce an algorithm in Python
Improve algorithms in terms of complexity
Understand commonly used data structures
Learn the notion of complexity classes
Plan
The first part of the course focuses on calculating the complexity of an algorithm, first in the non-recursive case and then in the recursive case. While the non-recursive case is simply a matter of counting the number of operations and requires only a knowledge of simple arithmetic, the recursive case is more complex and has its own tools, such as the general theorem. We also look at the notion of complexity classes and NP-hardness.
We then look at different data formats and their complexity for different elementary operations. Finally, we’ll look at how dynamic programming can be used to reduce the complexity of an algorithm.
Prérequis
Rudiment in imperative programming