Course on Probabilistic Algorithms, Chiang-Mai, December 2004

By Philippe Flajolet. This is the outline of a set of 10 lectures for the Fifteenth Asian School on Computer Science, December 11-15, 2004 following the ASIAN'04 Conference. Chiang Mai, Thailand. This will be mostly a course on "selected topics" as no reasonably complete coverage of the vast topic of probabilistic algorithms can nowadays be expected. Several of the examples discussed will be related to the area of Massive Data Sets. The general orientation of the course will be to focus on analytic-combinatorial methods.
Here is a detailed plan and some relevant references. Most are freely available and marked but this does not apply to two of the books.


Probability, combinatorics, and algorithms

Reading: Principally the books by Flajolet-Sedgewick and Motwani-Raghavan. Unfortunately they are only available commercially. The Vitter-Flajolet chapter is freely available on the web (though without figures, because of the technology of the time). Standard texts on ALGORITHMS (only commercially available): these are only indirectly needed for the course, but anybody seriously interested in algorithms and data structures should have consulted them.

Random allocations

Reading:

Digital trees and applications

Reading:

Probabilistic counting and LogLog Counting

Reading:

Frequency moments and stable laws

Reading: