Discrete mathematics II : Algorithms and complexity

Teacher(s)

Blondel Vincent; Delvenne Jean-Charles; Delvenne Jean-Charles (compensates Blondel Vincent);

Language

English
> French-friendly

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.

Learning outcomes

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) Worst case and average case complexity: upper and lower bounds, information-theoretic methods, Yao lemma, illustration on elementary algorithms (sorting, efficient implementation of data structures).
b) Energetic cost of computing: theory (Landauer's bound) and practice.
c) Some strategies of design of algorithms including divide-and conquer, dynamic programming, greedy methods.
d) Probabilistic algorithms: Monte Carlo and Las Vegas methods. Pseudo-random generators. Derandomisation. 
e) Aspects of complexity theory: complexity classes (deterministic, non-deterministic or probabilistic ; uniform or non-uniform).
f) Quantum computing: qubits, no-cloning theorem, Grover's and Shor's algorithms, prospects.

Teaching methods

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

Evaluation methods

The students are evaluated during the exam session through an individual written (or oral, depending on the circumstances) exam, on the objectives listed above. It counts for 75% of the final grade. Moreover the students write homework papers during the term. The grades for the papers amount to 25%  of the final grade (in Jan and, unchanged, in 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

> MAP