INF 413 A: Advanced Analysis of Algorithms

Presentation

The aim of this course is to present an approach which is and evidently will remain stable for a long time regardless of technical and technological mutations.

In fact, contrary to systems which are always undergoing the stress of their time and which respond to the demands of permanently evolving aims, this course presents the fundamental principles of computer science, particularly the algorithm.

Even today the typical image of computer science is unfairly reduced to that of a machine and a human trying to solve a problem. This image , which owes a lot to the banalisation of computer science is simply the media element of a proper science which expresses its principles, methods, demands and values. It is also a poor image in that it hids several aspects of a discipline whose increasing complexity is reflected in its presence in almost every sector of human activity today. It is and will remain unthinkable to conceive of a type of engineer today or tomorrow without informatics skills. Even if they won’t have to program themselves they have and will have to juggle with the potential of computing.

This potential is inscribed in the foundational state of computer science in that it commands the whole by preceding and situating all other practical aspects. It defines, in advance the horizon and limits evolution to what is or seems technically possible.
So firstly we shall speak od problems and their resolution without worrying about the effective mediation of machines and languages. Secondly we shall study the effective passage of algorithmic solutions brought to machines. This second part will be an introduction to programming.

Objectives

It is precisely these major ideas which constitute the ambition of this course. A course which willingly accepts the comfortable but limiting opposition between theory and practice and aims at an intermediary pedagogical and more binding dimension. We will pay particular attention to the complexity of the studied algorithms.

Duration: 21h

Organization

Scheduled activities

• C1 (1h30)   Les structures de données
• PC1 (1h30)   Les arbres binaires de recherche
• TPE 1/2 (3h)   Introduction à Python
• C2 (1h30)   Les tables de hachage et la recherche de chaînes de caractères
• PC2 (1h30)   Fonction d’adressage - Algorithme de Rabin-Karp
• CONF 1/2 (3h)   L'algorithmique dans l'entreprise
• C3 (1h30)   Algorithme génétique
• PC3 (1h30)   Algorithme génétique
• TP 3/4 (3h)   Etude de K-means (1)
• TPE 5/6 (3h)   Etude de K-means (2)

Team

Educational resource

Transparents de cours. Page moodle du module.

Recommended reading

Bibliographie donnée à l'intérieur des polycopiés:
- Introduction to Algorithms, Third Edition; Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Cliff Stein; MIT Press and McGraw-Hill; ISBN-10: 0262033844; http://mitpress.mit.edu/algorithms/
- Teach yourself Data Structures and Algorithms in 24 hours; Robert Lafore; Sams; ISBN-10: 0672316331
- Computational Geometry: Algorithms and Applications;
Third Edition (March 2008); Mark de Berg, TU Eindhoven (the Netherlands); Otfried Cheong, KAIST (Korea); Marc van Kreveld, Mark Overmars, Utrecht University (the Netherlands); published by Springer-Verlag