Session 5

Advanced algorithmics

Presentation and objectives

Many problems can be solved in an algorithmic way. After several decades of searching for efficient algorithmic solutions, some families of techniques have emerged. New problems are usually nothing more than special cases of old and well-known problems. This session will introduce you to a number of existing algorithmic strategies together with the problem solving situations where they apply.

Algorithmics

On the algorithmics part, you will discover the following techniques:

• divide and conquer
• greedy algorithms
• memorisation and dynamic programming

You will see when they apply, how they relate to recursion, and how they compare one to the other, with their respective strengths and weaknesses.

Additional material: backtracking?

Left aside: heuristics?