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.
Teaching : 20h lecture + 40h practical work
Examination : practical works + final exam
Lecturer : Fabien Baldacci
- 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