Applied Algorithm Design
- The goals of this course are 1) to survey the foundations of the design and analysis of algorithms; 2) to provide a practical understanding of complexity theory and algorithmics; 3) to provide an in-depth understanding of selected problems at theforefront of research explorations in the design and analysis of algorithms.
- Most of the excercises and examples are drawn from problems related to networking and distributed systems, such as peer-to-peer systems. More traditional cases are also covered in the Lectures.
- The material presented during class is used by students as a complementary text book. Lecture notes and slides are mainly based on the material presented in the excellent book from J. Kleinberg, E. Tardos. In many cases, the slides report examples and text of their book. I also used some slides (especially those with animations) from [Prof. Kevin Wayne]. J. Kleinberg, E. Tardos. Algorithm Design. Addison-Wesley, 2005 T. H. Cormen, C. E. Leiserson, R. L. Rivest. Introduction to Algorithms. Mc Graw-Hill S. Dasgupta, C. H. Papadimitriou, U. V. Vazirani. Algorithms. Mc Graw-Hill
Basic knowledge of elementary data structures, sorting, and basic terminology involving graphs (including the concepts of depth-first search and breadth-first search). Some of these are reviewed in the course. The lectures and homework may involve the analysis of algorithms at a fairly mathematical level: students are expected to be comfortable reading and writing proofs.
Nb hours per week: 3.00