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

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
• November 16, 19: Sections 22.4, 26.1, beginning of 26.2
• November 23, 26: Sections 26.2 continued, 26.3
• November 30, December 3: Sections 21.1, 21.2, 21.3, Chapter 23
• December 7, 10: Sections 24.1, 5.1, 5.2
• December 14, 17: Sections 11.1, 11.2, 8.1, 8.2 + Discussion of Quicksort
• December 21: Review

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

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 exam takes place Wednesday 16.01.2013 from 16h15 to 19h15 (CO3, CO010, CO2, CO1).

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