As a result of the Corona crisis some course information may have altered. Do check your course announcements in Blackboard!

# Data structures and graph algorithms

 Course Code : 1001WETDGR Study domain: Computer Science Academic year: 2019-2020 Semester: 2nd semester Sequentiality: 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
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