# Discrete mathematics II : Algorithms and complexity

linma2111  2020-2021  Louvain-la-Neuve

Discrete mathematics II : Algorithms and complexity
Due to the COVID-19 crisis, the information below is subject to change, in particular that concerning the teaching mode (presential, distance or in a comodal or hybrid format).
5 credits
30.0 h + 22.5 h
Q1
Teacher(s)
Blondel Vincent; Delvenne Jean-Charles; Delvenne Jean-Charles (compensates Blondel Vincent);
Language
English
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 AA1 : 1,2,3 AA3 : 1,3 AA4 : 1 AA5 : 1,2,3,5,6 At the end of this course the student will be able to : Study exact and approximate algorithms for combinatorial problems from different viewpoints: design, data structure, performance analysis, existence, complexity. Apply some general techniques (divide and conquer, dynamic programming, etc.) to solve basic algorithmic problems (e.g. sorting) and perform a worst-case or average-case complexity analysis. Take initiatives to search information relevant for the analysis of a given problem.  Propose original solutions and compare them to available solutions. Write a report on the proposed and available solutions.
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 divide-and conquer, dynamic programming, greedy methods. c) Probabilistic and quantum algorithms. d) Aspects of complexity theory including NP-completeness, complexity classes (deterministic or probabilistic) and decidability.
Teaching methods

Due to the COVID-19 crisis, the information in this section is particularly likely to change.

The course is organised in lessons and homework. No compulsory on-site exercise sessions.
Evaluation methods

Due to the COVID-19 crisis, the information in this section is particularly likely to change.

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 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.
Teaching materials
• Documents sur le Moodle / Documents on Moodle
Faculty or entity
MAP
Force majeure
Evaluation methods
The exam is written, on site. An exam of adapted form will be proposed to the students with a valid quarantine certificate or a 'formulaire retour' from the Foreign Office, if the teachers (Gautier Krings and Jean-Charles Delvenne) are warned asap and in any case before the main exam. This alternative exam will cover the same topics as the main exam, and will be organised in a form compatible with the situation of the student.

#### Programmes / formations proposant cette unité d'enseignement (UE)

Title of the programme
Sigle
Credits
Prerequisites
Aims
Master [120] in Electrical Engineering

Master [120] in Mathematical Engineering