Datastructuren en graafalgoritmen

Studiegidsnr:1001WETDGR
Vakgebied:Informatica
Academiejaar:2017-2018
Semester:2e semester
Contacturen:30
Studiepunten:3
Studiebelasting:84
Contractrestrictie(s):Geen contractrestrictie
Instructietaal:Nederlands
Examen:2e semester
Lesgever(s)Benny Van Houdt

Deze cursusinformatie is bedoeld om de student te ondersteunen bij het verwerken van de leerstof

3. Inhoud *

Deze cursus behandelt enkele van de meest elementaire en fundamentele graafalgoritmen, zoals graph searching, flow netwerken, matching algoritmen, opspannende bomen, etc. Verder worden een aantal geavanceerde data structuren die snelle implementaties van deze algoritmen toelaten in detail besproken en geanalyseerd. Een Engelstalige inhoudstafel van de cursusinhoud wordt hieronder  gegeven:

Contents:
GRAPH SEARCHING
1) Graph representations
2) Breadth-first Search (BFS)
3) The Depth-first search (DFS)
4) Topological sort

FLOW NETWORKS
1) Definitions and basic properties
2) The Ford-Fulkerson method (1956)
3) Performance of the Ford-Fulkerson algorithm
4) The Edmonds-Karp algorithm (1969)
5) Preflow-push algorithms
6) Performance of the Preflow-push algorithm

BIPARTITE MATCHING ALGORITHMS
1) The graph matching problem
2) A network flow solution
3) The Hopcroft-Karp algorithm (1973)
3.1) The algorithm and its number of iterations
3.2) Implementing a single iteration

DISJOINT-SETS DATA STRUCTURES
1) Disjoint-sets operations and the linked-list representation
2) Disjoint-sets forest

SPANNING TREES
1) Basic properties and definitions
2) Kruskal’s algorithm (1956)
3) Prim’s algorithm (1957)
3.1) Prim’s algorithm and binary heaps
3.2) Graph preprocessing for sparse graphs

FIBONACCI HEAPS
1) Introduction
2) Definition and elementary operations
2.1) The delete-min operation
2.2) The decrease-key operation
3) Amortized analysis
3.1) Amortized analysis of the delete-min and decrease-key operation
4) Bounding the maximum degree