Attention: Since the academic year 2015/16, all course communication is via the Moodle system (for which you need to be enrolled in the course). The page below is for the year 2014/15 only. I keep it because it gives non-enrolled students a first idea what the course is like.

INF421: Design and Analysis of Algorithms

Responsable Teacher: Benjamin Doerr

Note: The course "Les bases de la programmation et de l'algorithmique" with course number INF421 up to X2012 is now called INF411. This is the webpage of the new course INF421 "Design and Analysis of Algorithms" taught for the first time autumn 2014 (X2013).

Synopsis of the Cours

Algorithms are the heart of all computation. This course, building on the algorithmic foundations laid in the first computer science courses (INF321 or INF311+INF411), equips the student with a solid background in modern algorithmics. Having followed this course, the student will have a profound knowledge of the most central algorithms, both understanding how and why they work and being able to solve a wide range of computational problems with these building blocks. This is material that everyone aiming to work in a computer science or computing related context needs to know, let it be in a research or industrial environment. In addition to this, we shall also give a brief introduction to several more recent topics like randomized algorithms, evolutionary algorithms, online algorithms, or algorithmic game theory, which had a significant impact on how we understand computing today.

Overview of the Topics Covered

PC, TD, Programming Project

The course comes with a mix of PC and TD. As other courses in the 4xy series (x ≥ 2), it is possible to do a programming project related to the course. The formal rules are the same for all 4xy courses (each student can do at most one project, students planning to do their PA in computer science need to do one project). The details will be discussed at the start of the course.

Devoirs à la maison (DM)

Travaux Dirigés (TD)

Languages: English or French, Pseudo-code, Java

Teaching language: The course itself (that is, the Amphis) will be taught in English. For the PC, TD, and programming project, students have the choice between English and French. We will make sure that no-one suffers from language problems. The exam can be taken in either language, even a mix of both is allowed.

Programming language: The aim of this course is understanding algorithms. It is not a programming course. We will implement algorithms whenever it helps understanding them (mostly in the TD). We will use Java as taught in the predecessor courses INF321 / INF311+411.

Poly

Since this is a new course, a poly will be distributed chapter-wise before the lecture (but all chapters before the Christmas break).

History

Since this is a new course, no teaching material from previous years exists. This course will contain some of the algorithmic content of INF431 (up to X2012), but observe from the course description above that this course will contain many new topics. This webpage will gradually be extended, so come back once a while for more information. Feel free to contact me (Benjamin Doerr), e.g., via email lastname@lix.polytechnique.fr, if you don't want to wait.