Algorithms 4

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

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

transversal use of randomness in algorithms, through the introduction of the concept of probabilistic algorithms and the study of hash tables, which are an intrinsically probabilistic data structure.