Note from June 29, 2020
Although we do not yet know how long the social distancing related to the Covid-19 pandemic will last, and regardless of the changes that had to be made in the evaluation of the June 2020 session in relation to what is provided for in this learning unit description, new learnig unit evaluation methods may still be adopted by the teachers; details of these methods have been - or will be - communicated to the students by the teachers, as soon as possible.
Although we do not yet know how long the social distancing related to the Covid-19 pandemic will last, and regardless of the changes that had to be made in the evaluation of the June 2020 session in relation to what is provided for in this learning unit description, new learnig unit evaluation methods may still be adopted by the teachers; details of these methods have been - or will be - communicated to the students by the teachers, as soon as possible.
5 credits
30.0 h + 22.5 h
Q1
Teacher(s)
Blondel Vincent; Delvenne Jean-Charles (coordinator);
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 non-numerical aspects. A mathematical analysis of the existence and complexity of algorithms for classic problems pertaining to discrete structures and problems. Previous exposition to non-elementary 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 non-numerical 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.
Aims
At the end of this learning unit, the student is able to : | |
| 1 |
|
The contribution of this Teaching Unit to the development and command of the skills and learning outcomes of the programme(s) can be accessed at the end of this sheet, in the section entitled “Programmes/courses offering this Teaching Unit”.
Content
Introduction to the basic algorithms for sorting and the efficient implementation of different data structures including an analysis of worst case and average case complexity. Treatment of important algorithm classes including greedy and dynamic programming algorithms. Aspects of complexity theory including NP-completeness, complexity classes and decidability.
Teaching methods
The course is organised in lessons and weekly homework, for which non-compulsory consulting is offered.
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, which are corrected and commented. The grades for the homework enter the final grade.
Online resources
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.
Faculty or entity
MAP
