Algorithm designs and analysis
Teaching goals
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.
Course description
- Algorithm Analysis, Complexity
- Data Structures: Heap and Tree
- Graph algorithms
- Turing Machine, Computability
- Reduction between hard problems
- Complexity Classes (Time, Space)
Keywords
Analysis of Algorithms, Complexity, Reductions, Hard problem.
Prerequisite
Algorithms will be coded in C.
Bibliography
- 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
Biography
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.