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 |

At the start of this course the student should have acquired the following competences:

an active knowledge of

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).

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

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

The course has an international dimension.

Class contact teachingLectures Practice sessions

Personal workExercises

Personal work

ExaminationWritten examination without oral presentation Closed book Open book

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

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.

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