SDA

Data structures and algorithms

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)