Graph algorithms

For year 2023-2024, there is a team created on MS Teams. Access code: nj2krlo

The final exam will take place, for all groups except 914, during the last lecture (2024-06-05 16:00-18:00 room A2). For group 914, it will be on Friday (2024-06-07, at 8:00-10:00, room C335). Students that cannot take the exam with their own group and want to come with the other must write me in advance.

Lectures

• Glossary
• Graph representation
• Graph traversal
• Strongly connected components
• Minimum cost walks by dynamic programming and Ford's algorithm
• Dijkstra's algorithm and A* algorithm
• Minimum cost walks for all pairs of vertices
• Directed acyclic graphs (DAGs)
• Trees
• NP-hard problems
• Transport graphs and flows
• Maximum flow of minimum cost

Basic definitions (pdf), incomplete, as of 2007-10-05

Lecture notes from Professor Kasa's webpage, translated into PDF format.

Seminary

• (S1) modeling real problems with graphs
• (S2) Graph representations
• (S3) Breadth-first and depth-first search (python)
• (S4) Dijkstra and Bellman min-cost path algorithms
• (S5) Directed acyclic graphs (DAGs)
• (S6) Trees

Practical works

• Practical work no. 1
• Practical work no. 2
• Practical work no. 3
• Practical work no. 4
• Practical work no. 5

Requirements and grading

• Exam subjects sample

Misc. items

Vector and matrix data types in c++ (example)