Data structures and graph algorithms

Course Code :1001WETDGR
Study domain:Computer Science
Academic year:2017-2018
Semester:2nd semester
Contact hours:30
Credits:3
Study load (hours):84
Contract restrictions: No contract restriction
Language of instruction:Dutch
Exam period:exam in the 2nd semester
Lecturer(s)Benny Van Houdt

3. Course contents *

This course introduces and analyzes the following graph networking problems and advanced data structures:

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