Algorithm Design and Analysis
Crédits ECTS :
Heures de cours :
Heures de TD :
Modalité d'examen :
This course aims at providing students with basic and more advanced notions of algorithm design and analysis. It covers important algorithmic techniques and their applications to various classical problems. For each algorithm studied, the course insists on data structures and implementation, and on complexity analysis. The goal is not to give an exhaustive review of existing algorithms, but rather to understand broad techniques that can then be reused in whatever problems the students will face in the future.
The course emphasis is on methods and their theoretical analysis but a small number of selected algorithms will be implemented (in Python). The course gives methods that are generically useful for coding interviews, pointers will be given to students who want to train specifically for that exercise.
The required background for this course corresponds to the computer science courses of the 1st year of ENSAE, that is: basic familiarity with computer science, algorithms, and programming (in Python).
The following outline is tentative and subject to changes depending on the speed of progress.
Flows, cuts, and matching
Application of linear programming to algorithms
Advanced topics: approximation algorithms, random algorithms, heuristics
Jon Kleinberg and Eva Tardos. Algorithm Design. Pearson, 2005.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein. Introduction to Algorithms, Fourth Edition. MIT Press, 2009.
Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani. Algorithms. McGraw-Hill Education, 2006.
Gayle Laakmann McDowell. Cracking the Coding Interview: 189 Programming Questions and Solutions, 6th Edition. CareerCup, 2015