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 you are free to choose the final exam in either of English or French. The exercises will be mainly in English but some may be 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 GCA331, GCB330 and GCC330)

Office hours are Tuesdays 14:00-15:00, Thursdays 14:00-15:00, Fridays 15:30-16:30 (room BC150).

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

• September 21, September 24: Sections 2.1, 2.2 + Review of Chapter 1 and Appendix A
• September 28, October 1: Sections 2.3, 4.1 + Review of Chapter 3
• October 5, 8: Sections 4.2, 4.4, 4.5 + Review of Section 4.3
• October 12, 15: Chapter 6
• October 19, 22: Sections 10.1, 10.2, 12.1, 12.2, 12.3
• October 26, 29: Sections 15.1, 15.2
• November 2, 5: Sections 15.3, 15.4, 15.5
• November 9, 12: Sections 22.1, 22.2, 22.3 + Review of Appendix B

The textbook for the course is:

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

Librairie-papeterie La Fontaine (EPFL - Rolex Center) has promised to provide copies of the textbook.

For the curious student, some subset of the topics covered in the course has been treated also in the interesting set of books The Art of Computer Programming by Donald E. Knuth.

For the exercise sessions, seat in the exercise rooms according to the beginning of your last name as follows:

A to Ek: GCA331

El to Me: GCB330

Mf to Z: GCC330

The handouts (exercises and their solutions) as well as slides will be uploaded on the course moodle: http://moodle.epfl.ch/

You are allowed to use an A4-page on which you can write anything on both sides. (You are not allowed to look at it using a magnifying glass!)

The final exam has 100 points. There will be also bonus quizzes every two weeks during the semester in the discussion sections, from which you can gain 30 points.

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