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'll look at exhaustive search and backtrack algorithms, which provide exact solutions relatively efficiently in practice. On the other hand, we'll look at approximation algorithms, which provide only approximate solutions, but with much lower complexity. In algorithm analysis, we'll go beyond worst-case analysis to tackle average analysis (when input data is random) and amortized analysis (when the same operation is performed several times in succession). Finally, we'll take a look at

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