Algorithms
Credits 
6 
Lecturer 
Michael Kapralov

Schedule 
Lectures: Mondays 1416 in CE6 and Fridays 1315 in CO1.
Exercises: Mondays 1618 with quiz in GCA 331 (A to Cl), GRA 330 (Co to Ga), GCB 330 (Ge to Li), GR B3 30 (Lo to Sa), GCB 331 (Sc  Z).
On Mondays without a quiz we only use GCA331, GCB330, and GCB331 assuming there is enough room.

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
NPcompleteness.
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.
For more details see the official couse book here.
Important dates

Midterm exam: Friday 17 November

Quizzes: The following Mondays: 2 Oct, 16 Oct, 30 Oct,
27 Nov, 11 Dec, 4 Dec, 18 Dec

Final Exam: February 1st
Calendar
Here, you can see the times of office hours, lectures, etc..
Weekbyweek material
This list is very preliminary.
 September 22, September 25: Basic concepts and analysis + Insertion Sort. Sections 2.1, 2.2 + Review of Chapter 1,3 and Appendix A
 September 29, October 2: DivideandConquer, Mergesort, solving recurrences,
maximumsubarray problem. Sections 2.3, 4.1, 4.34.5
 October 6, 9: Strassen's algorithm for matrix multiplication, solving recurrences. Sections 4.2, 4.4, 4.5 + Review of Section 4.3
 October 13, 16: Heaps and Heapsort. Chapter 6
 October 20, 23: Datastructures: queues, linked lists, binary search trees. Sections 10.1, 10.2, 12.1, 12.2, 12.3
 October 27, 30: Dynamic programming: rod cutting matrix chain multiplication. Sections 15.1, 15.2
 November 3, November 6: More Dynamic Programming: formalization, longest common subsequence, optimal
binary search trees. Sections 15.3, 15.4, 15.5
 November 13, November 17: Elementary graph algorithms: BFS, DFS, Sections 22.1, 22.2, 22.3 + Review of Appendix B
 November 20, November 24: Topological sort, flows. Sections 22.4, 26.1, beginning of 26.2
 November 27, December 1: Flows continued and bipartite matching. Sections 26.2 continued, 26.3
 December 4, December 8: Datastructure disjoint sets + minimum spanning trees. Sections 21.1, 21.2, 21.3, Chapter 23
 December 11, December 15: BellmanFord, probabilistic analysis. Sections 24.1, 5.1, 5.2
 December 18, December 22: Hash tables, Sections 11.1, 11.2, 8.1, 8.2 + Discussion of Quicksort
Reading
The textbook for the course is:

Thomas Cormen, Charles Leiserson, Ronald Rivest, Clifford Stein: Introduction to algorithms, Third
Edition, MIT Press, 2009.
Exercises
For the exercise sessions during the quiz, seat in the exercise rooms according to the beginning of your last name
as follows:
A to Cl: GCA 331
Co to Ga: GRA 330
Ge to Li: GCB 330
Lo to Sa: GR B3 30
Sc to Z: GCB 331
On Mondays without a quiz, we only use GCA331, GCB330, and GCB331 assuming that there is sufficient room.
Handouts
The handouts (exercises and their solutions) as well as slides will be uploaded on the course
moodle:
http://moodle.epfl.ch/
Midterm and Final Exam
You are allowed to use a
hand written A4page on which you can write anything on both sides. (You are not allowed to look at it using a magnifying glass!)
Grading
The final grade will be the maximum between (i) the score obtained at the final and (ii) 10% quizzes
+ 30% midterm + 60% final.
Homepage of other editions of this course
20122013, 20112012, 20102011, 20092010, 20072008, 20062007