# 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 |

### 1. Prerequisites *

an active knowledge of

- Dutch

- Dutch
- English

This course discusses some fundamental graph algorithms and their corresponding data structures. A lot of emphasis is put on the correctness and the time/memory complexity of the various algorithms and data structures discussed throughout the course. Some basic knowledge of a number of classical data structures is required (e.g., linked list, queue, stack, binary trees) . Additionally, some prior knowledge on the complexity theory of algorithms is a plus (e.g., big-O notation).

### 2. Learning outcomes *

- The students become familiar with some fundamental graph network algorithms and their associated advanced data structures.
- The students ought to be able to develop algorithms for closely related graph networking problems.
- The students should also be able to identify and recognize typical computer science problems that can be rephrased as a graph networking problem.

### 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

### 4 International dimension*

The course has an international dimension.

### 5. Teaching method and planned learning activities

Personal work

### 6. Assessment method and criteria

Continuous assessment

### 7. Study material *

#### 7.1 Required reading

Detailed course notes in English (~60-pages) are made available to the students

**7.2 Optional reading**

The following study material can be studied voluntarily :

Introduction to Algorithms, written by T.H. Cormen, C.E. Leiserson

and R.L. Rivest and published by MIT Press, 2001.

Data Structures and Network Algorithms by R.E. Tarjan published

by CBMS-NSF Regional Conference Series in Applied Mathematics, 1983.

### 8. Contact information *

For questions and remarks, please contact Benny Van Houdt in room G222 (after making an appointment by email).