| Course label : | Algorithms and their complexity 2 |
|---|---|
| Teaching departement : | EEA / Electrotechnics - Electronics - Control Systems |
| Teaching manager : | Mister PIERRE-ANTOINE THOUVENIN / Mister PIERRE CHAINAIS |
| Education language : | |
| Potential ects : | 0 |
| Results grid : | |
| Code and label (hp) : | MR_DS_S2_AC2 - Algo and their complexity 2 |
Education team
Teachers : Mister PIERRE-ANTOINE THOUVENIN / Mister PIERRE CHAINAIS
External contributors (business, research, secondary education): various temporary teachers
Summary
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.
Educational goals
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.
Sustainable development goals
Knowledge control procedures
Continuous Assessment
Comments: Labs, grading scale: (min) 0 – 20 (max)
Exam, grading scale: (min) 0 – 20 (max)
Online resources
Introduction to Algorithms (Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest e Clifford Stein) – McGraw-Hill.
Pedagogy
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.
Sequencing / learning methods
| Number of hours - Lectures : | 12 |
|---|---|
| Number of hours - Tutorial : | 12 |
| Number of hours - Practical work : | 0 |
| Number of hours - Seminar : | 0 |
| Number of hours - Half-group seminar : | 0 |
| Number of student hours in TEA (Autonomous learning) : | 0 |
| Number of student hours in TNE (Non-supervised activities) : | 0 |
| Number of hours in CB (Fixed exams) : | 0 |
| Number of student hours in PER (Personal work) : | 0 |
| Number of hours - Projects : | 0 |
Prerequisites
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.