Algorithmic and Complexity

The goal of this course is to introduce computer science methods for engineering problem solving. It presents different problem families using theoretical models. It shows how to solve these problems using exact or approximation algorithms. We question the existence of a solution and we take great care to the quality of the computed solution. We study the complexity of the problems as well as the complexity of the resolution algorithms.

Click here to access the course website.

Teaching time performed: 81 hours of tutorials.

Part of the teaching team for the school years 2020-2021 and 2021-2022.

Instructors: Safouan TAHA (2020-2021) then Lina Ye

Student level: First year (~L3/BSc).

Syllabus

• Lecture 1: Introduction and graph traversals.
• Lecture 2: Shortest paths algorithms.
• Lecture 3: Minimum spanning trees.
• Lecture 4: Flow graphs.
• Lecture 5: Data Structures.
• Lecture 6: Dynamic Programming.
• Lecture 7: Theory of complexity.
• Lecture 8: Approaches for hard problems.