Algorithm and Complexity

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.

This site uses cookies to improve your user experience and to achieve audience statistics.
I acceptI refuseKnow more