Course Syllabus 2014/2015

Module : IF206

Title :

Prerequisite :

Title :

Randomized Algorithms

Number of hours : Combined lecture and tutorial classes : 28.00 h

Individual work : 13.50 h

ECTS credits : Individual work : 13.50 h

3.00

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.

Plan : Some complements on probability theory are included.

- Introduction

Two examples: sorting and minimal cut. Randomized algorithm models: Monte Carlo and Las Vegas. - Models

Definition of random sources. Comparison between models of sources. Random and pseudo-random sources. - Some examples from number theory

A little modular arithmetic. Modular square roots. Miller-Rabin primality testing - Randomized selection
- Probabilistic data structures

General description. Skip lists. Treaps. Hashtables

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