Course teacher(s)
Jean CARDINAL (Coordinator)ECTS credits
5
Language(s) of instruction
english
Course content
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
Objectives (and/or specific learning outcomes)
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.
Prerequisites and Corequisites
Required and Corequired knowledge and skills
A good background in elementary probability theory and algorithm design.
Teaching methods and learning activities
Lectures, exercises, and individual programming assignments.
References, bibliography, and recommended reading
Randomized Algorithms, R. Motwani and P. Raghavan, Cambridge University Press, 1995.
Course notes
- Université virtuelle
Other information
Contacts
Jean Cardinal
email : jean.cardinal@ulb.be
Campus
Plaine
Evaluation
Method(s) of evaluation
- written examination
- Project
written examination
Project
Language(s) of evaluation
- english