Graph algorithms

For year 2025-2026, there is a team created on MS Teams. Access code: y3jxflv

Final written exam:

• Groups 912/2, 913, 914, 915, 916: Friday June 5th, 14:00-16:00, rooms Iorga (2/I) and Popoviciu (5/I)
• Groups 911, 912/1, 917: Friday June 5th, 16:00-18:00, room Calugareanu (6/II)
• re-sit exam: Saturday, July 11th, 8:00-10:00, room Calugareanu (6/II)

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
• Matching in a bipartite graph
• 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)