Algorithm Design and Analysis

Objectif

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.

Prerequisites 

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).

Plan

The following outline is tentative and subject to changes depending on the speed of progress.  

1. Greedy algorithms

2. Dynamic programming 

3. Graphs algorithms 

4. Flows, cuts, and matching

5. Application of linear programming to algorithms 

6. Advanced topics: approximation algorithms, random algorithms, heuristics

Références

• 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