Algorithmic Complexity

M1 course

I was in charge of this course at Université Paris Cité.

This course, destined to students in the first year of our Master in Computer Science program (M1), presents basic notions of computational complexity:

  • Turing machines and decidability,
  • time complexity: P, NP, coNP and the polynomial hierarchy,
  • space complexity: L, NL, PSPACE.

A quick look to more advanced concepts (Boolean hierarchy, parameterized complexity) concludes the course.

I am in charge of the lectures and tutorials. In 2023-2024, my teaching load is:

  • 15 hours of lectures,
  • 30 hours of tutorials.