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, but the students are free to choose the final exam in either of English or French. Of the exercises, some are in English and some in French.

• 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 is:

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

For the curious student, some subset of the topics covered in the course have been treated also in the interesting multi-volume book The Art of Computer Programming by Donald E. Knuth.

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!)

2011-2012, 2010-2011, 2009-2010, 2007-2008, 2006-2007