• ECTS

    5 credits

  • Component

    Faculty of Science

Description

This module explores some advanced topics in algorithm design and analysis.

Read more

Objectives

In algorithm design, techniques to tackle difficult problems will be presented. On the one hand, we will discuss exhaustive search and backtracking algorithms that provide exact solutions, relatively efficiently in practice. On the other hand, we will study approximation algorithms that provide only approximate solutions, but with a much lower complexity. In the analysis of algorithms, we will go beyond worst-case analysis to discuss average analysis (when the input data are random) and amortized analysis (when the same operation is performed several times in a row). Finally, we will see in a way

transverse the use of randomness in algorithms, via the introduction of the notion of probabilistic algorithm and the study of hash tables which are an intrinsically probabilistic data structure.

Read more