SDA

Data structures and algorithms

Description: This introductory course presents fundamental algorithms and data structures, as well as generic methods for efficiently solving computational problems. After a general introduction to algorithms and the concept of complexity, certain data structures are presented for their usefulness, such as hash tables, trees (particularly search trees), graphs, heaps, etc. Generic solution methods are then introduced through various examples, such as the divide-and-conquer principle, dynamic programming, and the class of greedy algorithms. Reference algorithms on graphs (Prim, Ford Fulkerson, Dijkstra, etc.) are presented in this context. The rest of the course deals with solving NP-hard problems using exact solution techniques (backtracking, branch-and-bound) and approximate techniques (polynomial time approximation schemes). The course concludes with the NPC class and the P=NP conjecture. The tutorials complement the various chapters of the course, focusing on specific problems. The practical work involves a project to design road navigation software spread over four sessions, drawing on all the chapters of the course.

Learning outcomes: At the end of this course, students will be able to identify the temporal and spatial complexities of an algorithm and place them in a hierarchy of complexity classes in order to evaluate their efficiency. They will be able to implement various generic techniques (dynamic programming, greedy algorithms, divide and conquer, etc.) to design an algorithm that is efficient in terms of complexity. Finally, they will be able to recognize the intrinsic difficulties of NP-hard problems and, where appropriate, use approximation algorithms rather than seeking an exact solution.

Evaluation methods: 3h written test, can be retaken.

Evaluated skills:

  • Development
  • Modelling

Course supervisor: Nicolas Jozefowiez

Geode ID: SPM-INF-009

CM:

  1. Introduction 1/2 (1.5 h)
  2. Introduction 2/2 (1.5 h)
  3. Problème de recherche et structures de données associatives 1/2 (1.5 h)
  4. Problème de recherche et structures de données associatives 2/2 (1.5 h)
  5. Graphes et parcours (1.5 h)
  6. Diviser pour régner (1.5 h)
  7. Programmation dynamique (1.5 h)
  8. Tas binaire et programmation dynamique (suite) (1.5 h)
  9. Algorithmes gloutons 1/2 (1.5 h)
  10. Algorithmes gloutons 2/2 (1.5 h)
  11. Problèmes NP-difficiles 1/2 (1.5 h)
  12. Problèmes NP-difficiles 2/2 (1.5 h)
  13. Problèmes NP-complets (1.5 h)

TD:

  1. Calcul de complexités (1.5 h)
  2. Graphes bipartis (1.5 h)
  3. Programmation dynamique (1.5 h)
  4. Problèmes NPC et algorithme d’approximation (1.5 h)

TP:

  1. Implémentation des graphes (4.0 h)
  2. Algorithmes géométriques (4.0 h)
  3. Plus court chemin dans un graphe (4.0 h)
  4. Problème du voyageur du commerce (4.0 h)