Algorithms designs and analysis
Objectifs pédagogiques
The goal of this course is to present the analysis of classical algorithms in the first part. The second part will present ‘hard’ problems, meaning problems that are difficult to solve, and their related complexity classes.
Description de cours
- Algorithm Analysis, Complexity
- Data Structures: Heap and Tree
- Graph algorithms
- Turing Machine, Computability
- Reduction between hard problems
- Complexity Classes (Time, Space)
Mots-clés
Analysis of Algorithms, Complexity, Reductions, Hard problem.
Prérequis
Algorithms will be coded in C.
Bibliographie
- Introduction to Algorithms (3rd edition), by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, 2009
- Introduction to the Theory of Computation (3rd edition), by Michael Sipser, 2012
Biographie de l’enseignant
Pierre-Alain Fouque is a Researcher Professor at the University of Rennes 1 and the Scientific Director of the CyberSchool. His research involves symmetrical public-key cryptography, proof of security protocols used in real life such as TLS or Signal, attacks by auxiliary canals, and the development of automatic attack detection tools by learning. His research is carried out at IRISA.