Faculty of Information Technology and Communication Sciences
Language of instruction
Technology and Natural Sciences
Mode of study
Algorithms for Graphs, 5 cr
Language of instruction: English, Finnish
The student is able to verify properties of relations and utilize these properties in analysis of information represented as graphs. For example, the student is able to define different relations using graph theory concepts.
For a given graph the student can identify the components, paths, cuts, spanning trees etc. The student can use algorithms for identifying components, paths, etc.
The student is able to recognize some common problems as graph problems and understands the basics of the algorithms that solve these problems. For example, shortest paths or minimal spanning tree.
The student understands how to prove the correctness of an algorithm via induction and loop invariants.
Basics of graph theory (paths, components, cuts)
Trees (root, parets, leaves, spanning trees)
Binary relations ( closures, order relations and related algorithms)
Proving algorithm correctness (loop invariants and induction)
Problem modeling with graphs (shortest path, flow problems, etc)
Graph and tree presentations (adjacency matrix, adjacency lists, etc)