5.00 credits
30.0 h + 22.5 h
Q1
Teacher(s)
Language
English
Prerequisites
This course assumes a sufficient mathematical maturity, equivalent to the level of a third year student in engineering. The course is an introduction to algorithmics, treating mainly of nonnumerical aspects. A mathematical analysis of the existence and complexity of algorithms for classic problems pertaining to discrete structures and problems. Previous exposition to nonelementary algorithmic questions is useful to the student; other than that, no prerequisite in algorithmics is assumed
Main themes
The course is an introduction to algorithms and their complexity from a nonnumerical point of view. The principal topic is the mathematical analysis of the existence of algorithms and their complexity on the classical problems of the field.
Learning outcomes
At the end of this learning unit, the student is able to :  
1 

Content
a) Illustration on basic algorithms for sorting and the efficient implementation of different data structures of the main concepts of the course, including an analysis of worst case and average case complexity. b) Treatment of important strategies of design of algorithms including divideand conquer, dynamic programming, greedy methods. c) Probabilistic algorithms. d) Aspects of complexity theory: complexity classes (deterministic, nondeterministic or probabilistic ; uniform or nonuniform) and decidability. e) Quantum computing: Grover's and Shor's algorithms.
Teaching methods
The course is organised in lessons and homework. No compulsory onsite exercise sessions.
Evaluation methods
The students are evaluated through an individual written exam, on the objectives listed above. Moreover the students write homework papers during the term. The grades for the homework amount to 25% of the final grade (in Jan and August).
Online resources
Moodle page of the course
Bibliography
 Algorithmics: Theory and Practice, G. Brassard and P. Bratley, Prentice Hall, 1988.
 Introduction to Algorithms, T.H. Cormen, C.E. Leierson and R.L. Rivest, MIT Press 1986.
 Notes on the Moodle page
Teaching materials
 Documents sur le Moodle / Documents on Moodle
Faculty or entity