FI:M015 Graph Algorithms - Course Information

M015 Graph Algorithms

Extent and Intensity

2/1. 3 credit(s). Recommended Type of Completion: zk (examination). Other types of completion: k (colloquium), z (credit).

Teacher(s)

doc. RNDr. Libor Polák, CSc. (lecturer)

Guaranteed by

Contact Person: doc. RNDr. Libor Polák, CSc.

Prerequisites

Before enrolling this course the students should go through M010 Combinatorics and Graph Theory.

Course Enrolment Limitations

The course is also offered to the students of the fields other than those the course is directly associated with.

fields of study / plans the course is directly associated with

• Informatics (programme FI, B-IN)
• Informatics (programme FI, M-IN)
• Upper Secondary School Teacher Training in Informatics (programme FI, M-IN)
• Upper Secondary School Teacher Training in Informatics (programme FI, M-SS)
• Information Technology (programme FI, B-IN)

Syllabus

• Elementary graph algorithms (representations of graphs, breadth-first search, depth-first search, topological sort, strongly connected components).
• Minimum spanning trees (growing a minimum spanning tree, the algorithms of Kruskal and Prim).
• Single-source shortest paths (shortest paths and relaxation, Dijkstra's algorithm, the Bellman--Ford algorithm, single--source shortest paths in directed acyclic graphs).
• All-pairs shortest paths (shortest paths and matrix multiplication, the Floyd-Warshall algorithm, Johnson's algorithm for sparse graphs).
• Maximum flow (flow networks, the Ford-Fulkerson method, maximum bipartite matching).
• Data structures for graph algorithms (binary heaps, priority queues, binomial heaps, data structures for disjoint sets).

Language of instruction

Czech

• Enrolment Statistics (Spring 1998, recent)
  
• Permalink: https://is.muni.cz/course/fi/spring1998/M015