| Libellé du cours : | Algorithms and their complexity 2 |
|---|---|
| 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_S2_AC2 - Algo and their complexity 2 |
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: • Tractable and intractable problems. • NP-algorithms, NP-hardness, NP-completeness. • Reductions. • NP-hard problems and linear programing. • Hard problems: Traveling salesman problem, Longest path, Hamilton cycle, Boolean circuit satisfiability, Clique, Vertex cover, Correlation Clustering. • Basic notions of probability (conditional probability, the law of total probability). • Approximation algorithms. • Analysis of approximation algorithms for graph problems. • Random graphs and basic notions related to random walk. • Hashing algorithms. Searching using Hashing. Hash tables. Hash functions. Some examples of hash functions. Collision resolution. • Basic problems related to randomized algorithms (e.g., Coupon Collector’s problem , Balls and Bins, …). • Chernoff Bound and its basic applications in the analysis of randomized algorithms. • Basic properties of randomized algorithms and methods for analyzing them. • Advanced data structures to solve specific problems taking into account computational constraints.
Objectifs pédagogiques
The goal of this course is to provide advanced algorithmic and computation notions covering the main topics related to randomized algorithms, relationships between different complexity classes, reductions and approximation algorithms. After successfully taking this course, a student should be able to: • Analyze average-case running times of algorithms whose running time is probabilistic. Employ indicator random variables and linearity of expectation to perform the analyses. • Manipulate problem reductions. • Know the relationships between different specific complexity classes (including complexity classes P, NP, L, NL, PSPACE, BPP, #P). • Design heuristics for complex problems. • Apply important algorithmic design paradigms and methods of analysis. • Argue the correctness of algorithms using inductive proofs. • Explain the basic properties of randomized algorithms and methods for analyzing them. Design algorithms that employ randomization. • Explain advanced graph algorithms and their analysis. • Design and analyze approximation algorithms.
Objectifs de développement durable
Modalités de contrôle de connaissance
Contrôle Continu
Commentaires: Labs, grading scale: (min) 0 – 20 (max)
Exam, grading scale: (min) 0 – 20 (max)
Ressources en ligne
Introduction to Algorithms (Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest e Clifford Stein) – McGraw-Hill.
Pédagogie
24 hours, 8 lectures 4 exercises. 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 programming knowledge and a background in algorithms and data structures, with a good understanding of the fundamental notions of probability. Algorithms and their complexity 1.