Advanced algorithm design - 4MM1AA

Goal(s)

Deepen the concepts introduced in the first year of algorithms.
Address efficient programming in terms of the number of operations and memory (cache misses).
Apply to solving difficult problems, particularly using implicit enumeration techniques.
Introduction to approximation algorithms, probabilistic algorithms, and interactive proofs.

Responsible(s)

Jean-Louis ROCH

Content(s)

1. advanced divide and conquer algorithms. Worst case and average cost analysis.
2. Analyzing Cache misses and cache oblivious programming.
3. Dynamic Programming
4. Branch&Bound
5. Complexity (polynomial hierarchy,: P, NP, PSPACE)
6. Approximation algorithms
7. Randomized algorithms (perfect hashing). Interactive prrofs (IP=PSPACE)

• • • This course is given in period 4 ***

L3 level in algorithms and programming:
basics in algorithms: data stucrutres -arrays, stack/deque, trees, priority queue, hash tables- and algorithms - graphs and shortest paths, divide and conquer, searching and sorting)
Practice in programming (eg python) and knowledge of C; iterative and recursive programming.
Basic knowledge in operation research (linear programming) and probabilities (Bernoulli law, Markov inequality)

Test

Evaluation : Examen écrit (3h)

Resit : Examen oral (exposé, soutenance, etc..) (30 min à 1h)

Written exam (3h), handwritten documents aithorized
TPs (to be completed at home and to deposit on teide)
Session 2
Oral examination (30mn to 1h of preparation)

Calendar

The course exists in the following branches:

• Curriculum - Work Study Education - Alternance periode 4 (2A)

Additional Information

Course ID : 4MM1AA
Course language(s):

The course is attached to the following structures:

• Team Programming and Software
• Team Search Algorithms-Programming-set operating

You can find this course among all other courses.

Bibliography

Cormen, Leiserson, Stein, Rivest, Introduction à l'algorithmique, Dunod, 2004