Course Syllabus 2015/2016
PDF Extract Anglais
Module : IF206
Title :
Randomized Algorithms
Number of hours :
Combined lecture and tutorial classes : 28.00 h
Individual work : 13.50 h
ECTS credits :
Teacher(s) :
DUCHON Philippe - Responsible
Level :
second year module
Abstract :
This course is an introduction to randomized algorithms, and studies the use of "randomized choices" in algorithms. The introduction is both theoretical and practical, and describes a number of efficient randomized algorithms, together with a careful performance estimation.

Some complements on probability theory are included.

Plan :
  1. Introduction
    Two examples: sorting and minimal cut. Randomized algorithm models: Monte Carlo and Las Vegas.
  2. Models
    Definition of random sources. Comparison between models of sources. Random and pseudo-random sources.
  3. Some examples from number theory
    A little modular arithmetic. Modular square roots. Miller-Rabin primality testing
  4. Randomized selection
  5. Probabilistic data structures
    General description. Skip lists. Treaps. Hashtables
Prerequisite :
IF101, IF102, IS101
Document(s) :
Lecture notes (in French) are available. The classical reference is: R. Motwani, P. Raghavan - Randomized Algorithms
Keyword(s) :
Probability theory, algorithms, analysis of algorithms