| Libellé du cours : | Algorithms and their complexity 1 |
|---|---|
| Département d'enseignement : | EEA / Electronique Electrotechnique Automatique |
| Responsable d'enseignement : | Monsieur PIERRE-ANTOINE THOUVENIN / Monsieur PIERRE CHAINAIS |
| Langue d'enseignement : | |
| Ects potentiels : | 0 |
| Grille des résultats : | |
| Code et libellé (hp) : | MR_DS_S1_AC1 - Algo and their complexity 1 |
Equipe pédagogique
Enseignants : Monsieur PIERRE-ANTOINE THOUVENIN / Monsieur PIERRE CHAINAIS
Intervenants extérieurs (entreprise, recherche, enseignement secondaire) : divers enseignants vacataires
Résumé
The course will cover the following topics: • Fundamental properties of algorithms. • Algorithm writing with pseudo-code. • Recursion. • Formal notational methods for stating the growth of resource needs (efficiency and storage) of an algorithm (Big Oh, Little oh, Theta notations). • Time and space complexity. • Best-case and worst-case complexity. • Divide-and-conquer paradigm. • Backtracking. • Branch-and-bound. • Dynamic programming. • Greedy algorithms.
Objectifs pédagogiques
This course gives an overview about algorithms and computation with a particular focus on the cost of algorithms. The overall goal is to be able to understand a range of algorithmic approaches, use them to solve practical problems, evaluate their cost, and compare the costs of different algorithms solving a given problem. After successfully taking this course, a student should be able to: • Write recursive algorithms, • Understand the following families of algorithms and use them to solve problems: divide-and-conquer, backtracking, branch-and-bound, dynamic programming, greedy algorithms. • Understand and evaluate the time and space complexity of an algorithm. • Analyze worst-case and best-case running times of algorithms using asymptotic analysis. • Derive and solve recurrences describing the performance of recursive and divide-and-conquer algorithms.
Objectifs de développement durable
Modalités de contrôle de connaissance
Contrôle Continu
Commentaires: Quizzes, grading scale: (min) 0 – 20 (max)
Homework, grading scale: (min) 0 – 20 (max)
Ressources en ligne
Introduction to Algorithms (Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest Clifford Stein) – McGraw-Hill.
Pédagogie
24 hours : 8 lectures, 8 tutorials. Language of instruction is specified in the course offering information in the course and program directory. English is the default language.
Séquencement / modalités d'apprentissage
| Nombre d'heures en CM (Cours Magistraux) : | 12 |
|---|---|
| Nombre d'heures en TD (Travaux Dirigés) : | 12 |
| Nombre d'heures en TP (Travaux Pratiques) : | 0 |
| Nombre d'heures en Séminaire : | 0 |
| Nombre d'heures en Demi-séminaire : | 0 |
| Nombre d'heures élèves en TEA (Travail En Autonomie) : | 0 |
| Nombre d'heures élèves en TNE (Travail Non Encadré) : | 0 |
| Nombre d'heures en CB (Contrôle Bloqué) : | 0 |
| Nombre d'heures élèves en PER (Travail PERsonnel) : | 0 |
| Nombre d'heures en Heures Projets : | 0 |
Pré-requis
This course requires some basic programming knowledge (expressions, variable, control flow statements, functions, arrays or lists) and some fundamental notions of mathematics (functions and sequences, recurrence relations). The knowledge of specific programming languages is not required.