année académique
2024-2025

Titulaire(s) du cours

Jean CARDINAL (Coordonnateur)

Crédits ECTS

5

Langue(s) d'enseignement

anglais

Contenu du cours

The course focuses on Randomized Algorithms:
  • Las Vegas and Monte-Carlo algorithms, examples : Minimum cut, binary space partitions
  • Randomized complexity classes
  • Game-theoretic techniques and Yao's Min-max principle
  • Moments and deviations : Randomized selection, coupon collector
  • Chernoff bounds
  • Randomized data structures and hashing

Objectifs (et/ou acquis d'apprentissages spécifiques)

An understanding of the theoretical foundations of randomness and probabilities in the design of efficient algorithms, and a hands-on experience on the programming of randomized algorithms.

Pré-requis et Co-requis

Connaissances et compétences pré-requises ou co-requises

A good background in elementary probability theory and algorithm design. 

Méthodes d'enseignement et activités d'apprentissages

Lectures, exercises, and individual programming assignments.

Références, bibliographie et lectures recommandées

Randomized Algorithms, R. Motwani and P. Raghavan, Cambridge University Press, 1995.

Support(s) de cours

  • Université virtuelle

Autres renseignements

Contacts

Jean Cardinal email : jcardin@ulb.ac.be téléphone : (02 650) 56 08

Campus

Plaine

Evaluation

Méthode(s) d'évaluation

  • Autre

Autre

Langue(s) d'évaluation

  • anglais

Programmes