Advanced Algorithmic

Description

This course gives the student the knowledge about standard data structures and algorithms on trees and graphs. It presents advanced data structures (heaps, self-balanced binary trees…) and complexity analysis of recursive algorithms. Graph algorithms (traversal, topological sort, shortest paths, flows…) are also detailed.

Furthermore notions of calculability and an introduction to the theory of Complexity (polynomial reductions, P and NP classes) are studied.


Organization

Teaching : 20h lecture + 40h practical work

Examination : practical works + final exam

Lecturer : Fabien Baldacci


Recommended Readings

  • T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduction to Algorithms, 3rd Edition, MIT Press
  • M. Sipser, Introduction to the Theroy of Computation, 3rd Edition