Session 5

Advanced algorithmics

Presentation and objectives

To be able to start the practical activity efficiently, we will introduce some needed concepts at the beginning of the class. To save you some time, we will present you a few slides, that you can find hereafter:

• Slides of the session.

These slides only cover the main elements of the course, and many more details are given in the associated articles. Thus, you should study the following articles at home after the session:

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.

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?

You can verify your understanding of these articles here:

• Self-assessment quiz.