Graph Algorithms

Fall 2026

Announcements

• [14/10]: Following department policy, the midterm exam (assuming it takes place) will only cover material which has been taught in person and not material taught online. As a result, the topics which are included on the midterm exam are the following: Lectures 1-3 (including BFS, DFS) and the first third of lecture 4 (topological sorting + definition of strongly connected components). The following topics are not included for the midterm: randomized algorithms, linear-time algorithm for strongly connected components and linear-time algorithm for articulation points.
• [14/10]: Due to the ongoing university closure the CM and TP sessions scheduled for tomorrow 15/10 are canceled (unless the university reopens tomorrow). Regarding TP1, please try to program the solution on your own and submit it by email to your chargé de TP to get feedback.
• [12/10]: Due to the university closure today and following the decision voted by the MIDO department last week, the TD/TP sessions scheduled for today 12/10 are canceled. We will update this page with further information throughout the week.
• [8/10]: A copy of last year's midterm exam subject can be found here.
• [6/10]: Due to the university closure, sessions scheduled for Thursday 8/10 will take place online. The information to attend the CM lecture at 12:00 is the following: link, Meeting ID: 394 300 223 187 216 4 Passcode: wJ6tn96C
• [6/10]: Further information on the closures. For the two TD groups of Thursday afternoon, the sessions will also take place via Teams. For the group taught by Ararat Harutyunyuan the information is: link, Meeting ID: 351 002 523 663 600 9, Passcode: E5R4ni6Y. For the group taught by Mohamed Anisse Belhadj the information is: link, Meeting ID: 311 793 790 592 541, Passcod: YN7DG9Ed.
• [10/9]: First class. Welcome!

General Information

The topic of this course is Graph Algorithms. Graphs are mathematical objects that can model complex networks with varying applications. In this course we will study algorithms that can resolve optimization problems on graphs, focusing mostly on theoretical analysis, but also considering practical programming implementations.

More information on the topics to be covered appears in the schedule below (which will be updated during the semester).

The course consists of 1.5 hours of weekly lectures, followed by 1.5 hours of TD (exercise sessions). For some weeks, the TD session will be scheduled to take place in a computer lab, to allow the students to program some of the algorithms we study. Check your online schedule for details.

Grading: Your final grade is the result of the formula 0.7E+0.3CC, where E is your grade in the final exam and CC is your grade in a midterm exam that will be organized at some point in the middle of the semester.

Additional Material / Bibliography

• Algorithms and Data Structures by K. Mehlhorn and P. Sanders.
• Algorithm Design by J. Kleinberg and E. Tardos.
• Introduction to Algorithms, by T. Cormen, C. Leiserson, R. Rivest, C. Stein.
• Interesting article about common errors in data structure performance analysis with Python (link).

Course Schedule

Here you will find a tentative schedule (updated regularly throughout the semester) and the slides we will use in class.

TD