Each module contains 3 ECTS. You choose a total of 10 modules/30 ECTS in the following module categories:

- 12-15 ECTS in technical scientific modules (TSM)

TSM modules teach profile-specific specialist skills and supplement the decentralised specialisation modules. - 9-12 ECTS in fundamental theoretical principles modules (FTP)

FTP modules deal with theoretical fundamentals such as higher mathematics, physics, information theory, chemistry, etc. They will teach more detailed, abstract scientific knowledge and help you to bridge the gap between abstraction and application that is so important for innovation. - 6-9 ECTS in context modules (CM)

CM modules will impart additional skills in areas such as technology management, business administration, communication, project management, patent law, contract law, etc.

In the module description (download pdf) you find the entire language information per module divided into the following categories:

- instruction
- documentation
- examination

This module introduces students with different categories of advanced algorithms and typical application areas.

In the first part of the module, the students will have a sound understanding of data structures and algorithms for efficiently handling either very large, complex or dynamic data sets or combinations thereof. They will be able to evaluate suitable algorithms and to apply them to typical tasks such as efficiently indexing, searching, retrieving, inserting or updating data such as large volumes of hypertext or spatial data.

The students will be familiar with dynamic algorithms used, for example, in artificial intelligence.

The second part of the module will present basic techniques for designing algorithms for hard combinatorial optimization problems. The combination of these basic components —problem modeling, problem decomposition, solution building, solution improvement, learning— lead to classical metaheuristics like genetic algorithms, ant colonies or tabu search. The students will be able to design new algorithms for hard combinatorial optimization problems and to apply them.

### Prerequisites

The student has working knowledge of:

- Geometry, linear algebra, algorithms (sorting, searching, hashing) and data structures (linear structures, trees)
- Basics of graph data structures and algorithms
- Algorithmic complexity, logic, probability theory.

These topics are generally contained in books introducing algorithms. For instance, chapters 1-12, 15-17, 22-26, 28-29, 34-35 of (Cormen 09) covers very well the prerequisites

### Learning Objectives

This module gives the student an overview of frequently used algorithms classes. Based on this strong foundation, students can design and implement the most suitable and efficient algorithms for use in their own applications. The student:

- is familiar with different categories of advanced algorithms and with typical application areas;
- has a sound understanding of data structures and algorithms for efficiently handling either very large, complex or dynamic data sets or combinations thereof;
- is able to evaluate suitable algorithms and to apply them to typical tasks such as efficiently indexing, searching, retrieving, inserting or updating data, including data types such as large volumes of hypertext or spatial data;
- is familiar with dynamic algorithms used in robotics, artificial intelligence.

### Contents of Module

Algorithms and data structures for selected practical problems. Weight 50%

- Reminder on linear structures, binary search tree, heap and algorithmic complexity
- Randomized algorithms (qsort, selection in linear time, kD tree, range tree, Delaunay triangulation)
- Deterministic algorithms(selection, kD tree)
- Sweep algorithms (closest pair of points, segment intersection)
- Greedy algorithms (Huffman code, Dijkstra, Fibonacci heap)

Design of heuristic algorithms. Weight 50%

- Reminder on complexity theory, combinatorial optimization problems, problem modelling
- Greedy heuristics
- Local search heuristics
- Decomposition methods
- Randomized heuristics
- Learning heuristics
- Classical metaheuristics: GRASP, ant colonies, tabu search, simulated annealing, noising methods, genetic algorithms

### Teaching and Learning Methods

- Ex-cathedra teaching
- Presentation and discussion of case studies
- Problem-based learning
- Theory and programming exercises

### Literature

M. de Berg, G. Cheong, M. van Kreveld, M. Overmars. Computational Geometry : Algorithms and Applications, Springer, Third Edition 2008.

T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein. Introduction to Algorithms, third edition, MIT Press, 2009.

P. Siarry (ed.), Metaheuristics, ISBN 978-3-319-45403-0, Springer, 2016.

H. H. Hoos, Th. Stützle Stochastic Local Search: Foundations and Applications, Morgan Kaufmann / Elsevier, 2004.

Éric D. Taillard

Design of Heuristic Algorithms for Hard Optimization

(Series: Graduate Texts in Operations Research)

Springer, 2023

ISSN 2662-6012

ISSN 2662-6020 (electronic)

ISBN 978-3-031-13713-6

ISBN 978-3-031-13714-3 (eBook)

Download full module description

Back