Description du contenu de l'enseignement :
This is an advanced algorithms course with an emphasis on topics that have applications in the treatment of large volumes of data and handling partially unknown information. The course is divided into two parts :
In the first part, the course discusses Randomized Algorithms and the use of probability theory in the design and analysis of algorithms. Topics that will be covered are applications of randomized techniques to sample and verify large volumes of data efficiently, the difference between average-case analysis and randomized worst-case analysis, and the application of randomized algorithms to cases where the input is only partially and gradually revealed (on-line algorithms).
In the second part, the course revisits traditional algorithm design techniques, such as divide&conquer, with a focus on optimizing performance to the point where the resulting algorithms can realistically be applied to big data problems. This part of the course places a particular emphasis on the notion of dynamic programming.
1. "Probability and Computing" by Mitzenmacher and Upfal
2. "Algorithms" by Dasgupta, Papadimitriou, Vazirani