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.
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 GCA331, GCB330 and GCC330)
The course starts on September 21st and ends on December 21st, 2012.
Week-by-week material
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
Reading
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.
Exercises
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
Final Exam
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).
Grading
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.
Homepage of the course in previous years