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).
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.
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.
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.
Since this is a new course, a poly will be distributed chapter-wise before the lecture (but all chapters before the Christmas break).
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.