In this course you will get familiar with the theory and practice of basic concepts and techniques in algorithms. The course covers mathematical induction, techniques for analyzing algorithms, elementary data structures, the design of algorithms by induction, Sorting and searching, Merge sort, quicksort, heapsort, binary search, graph algorithms and data structures, graph traversals, shortest paths, spanning trees, matching, network flows, and elements of the theory of NP-completeness.

This is a course for second year students of both the systèmes de communication and informatique sections. The main classes will be in english, while the exercise classes and course material will be in french.

The course starts on September 14th and ends on December 18th, 2009.

Due to popular demand, you can find the polycopies of the course here.

handouts click here

• The course notes.
• Udi Manber: Introduction to algorithms: A creative approach. (Addison Wesley publishing, 1989)
• Thomas Cormen, Charles Leiserson, Ronald Rivest, Clifford Stein: Introduction to algorithms. (MIT Press, 2001)

• Mondays : 14:15 - 16:00 - room CE6 (course)
• Mondays : 16:15 - 18:00 - room CE6 (exercice)
• Fridays : 13:15 - 15:00 - room CM1 (course)

There will be a midterm on November 2nd and a final some time in January (date not fixed yet). The final grade is a function of your performance on the midterm and your performance in the final exam. If M is your grade at the midterm, and F is your grade at the final exam, then your final grade G is obtained as follows:

• If M is smaller than or equal to the minimum of F and 4, then G = F
• Otherwise, G = F + (M-4)/2.