Algorithmics

Presentation & objectives

Welcome to the part of the course on algorithmics!

In this block, you will study how to solve problems using algorithmic solutions, i.e., series of operations that, when applied, compute a solution to the problem, pretty much like following a cooking recipee to make a cake.

In addition to writing algorithms, we will also study some properties of algorithms, such as complexity or termination. Indeed, it is important to be able to characterize these properties, either to be able to compare algorithms together (e.g, to determine which one to choose for a specific task), or to guarantee they will act as expected.

Finally, we will transition toward more advanced algorithmic solutions, and other approaches to solve problems. We will in particular give you an introduction on artificial intelligence, so that you know how it differs from classical algorithmic approaches.

Schedule

• Session 1 – Basics of algorithmics.

  Algorithmic statements, invariants, description of an algorithm.

• Session 2 – Recursion.

  Defining and writing recursive functions

• Session 3 – Data structures.

  Data structures (stack, queues) and their specificities.

• Session 4 – Properties of algorithms.

  Theoretical properties of algorithms: complexity, termination, deterministic/stochastic.

• Session 5 – Advanced algorithmics.

  Algorithmic strategies: divide and conquer, memoization and dynamic programming.

• Session 6 – Introduction to artificial intelligence.

  Basics of AI (supervised, unsupervised learning, models).

How is a session organized?

Most sessions will start with a quick presentation of key concepts by your teacher, with slides. These slides will only contain a summary of the notions you have to learn. Later, you will have to study a few articles to complement this presentation.

After this short introduction, you will have to work on exercises that put in practice the concepts of the session. In all practical activities, we ask that you start by disabling AI coding tools, so that you understand the fundamental concepts in the exercises. Later, you can do the exercises again with such tools activated to optimize your code.

Once the class is over, you have to make sure that you complete all non-optional exercises, and that you understand all concepts briefly introduced by the teacher, using the detailed articles. We provide you a few self-assessment quizzes to help you check your understanding. Do not hesitate to interact on the Discord platform!

Evaluation

The algorithmics block will be evaluated with a Wooclap MCQ on Moodle during session 6. At the beginning of the session, you will have to log in to Moodle and to answer a few questions, individually.

The goal is to verify your understanding of basic algorithmic elements (up to session 4 included), i.e.:

• Writing an algorithm.
• Understanding how recrsivity works.
• Understanding and using data structures and their specificities.
• Comparing algorithms based on their properties.

Algorithmics will also be evaluated during the final exam.