TSP

Algorithms

Credits 6
Lecturer Michael Kapralov
Schedule Lectures: Mondays 14-16 in CE6 and Fridays 13-15 in CO1.
Exercises: Mondays 16-18 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 NP-completeness.

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

Calendar

Here, you can see the times of office hours, lectures, etc..

Week-by-week material

This list is very preliminary.

Reading

The textbook for the course is:

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/

Mid-term and Final Exam

You are allowed to use a hand written A4-page 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% mid-term + 60% final.

Homepage of other editions of this course

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