This is an old revision of the document!


In this course you will get familiar with design and analysis of algorithms. The course covers

  • proving correctness of algorithms by mathematical induction
  • techniques for analyzing running time of algorithms
  • study of various sorting algorithms
  • elementary data structures as well as priority queues, binary search trees, and data structures for disjoint sets
  • the design of algorithms using divide-and-conquer and dynamic programming
  • graph algorithms including graph traversals, shortest paths, spanning trees, matching, and network flows
  • probabilistic analysis of algorithms.

This is a course for second year students of both the systèmes de communication and informatique sections. The lectures will be in English, while some of the exercises are in English and some may be in French. The students are free to choose the final exam in either of English or French.


  • Some programming experience, in particular understanding recursive procedures and simple data structures such as arrays and linked lists
  • Facility with mathematical proofs, especially proofs by mathematical induction
  • Some mathematical background including graphs and trees, counting and probability, matrices, summation formulas, elementary calculus: If you are not familiar with some of these or have forgotten them, you can review them in the Appendix at the end of your course textbook


  • Lectures on Mondays : 14:15 - 16:00 (room CE1) and Fridays : 13:15 - 15:00 (room CM1)
  • Exercise sessions on Mondays 16:15 - 18:00 (rooms BM5202, GCA331, GCB330 and GCC330)

The course starts on September 21st and ends on December 21st, 2012.


The textbook for the course will be

  • Thomas Cormen, Charles Leiserson, Ronald Rivest, Clifford Stein: Introduction to algorithms, Third Edition, MIT Press, 2009.

For a subset of the topics covered in the course, the multi-volume book “Art of Computer Programming” by Donald E. Knuth provides interesting treatment.


You are allowed to use an A4-age on which one can write anything on both sides.

Homepage of the course in previous years