This is an old revision of the document!
Algorithmique
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.
Prerequisites
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 mentioned bellow.
Schedule
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.
Reading
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.
Exam
You are allowed to use an A4-age on which one can write anything on both sides. (You are not allowed to look at it using a magnifying glass!)
Homepage of the course in previous years