Course Description -- Probabilistic Analysis of Algorithms and Data Structures

Computer Science 690
Probabilistic Analysis of Algorithms and Data Structures
August 7, 2023

Fall 2023 --- Course Syllabus

Instructor

Luc Devroye | Email | McConnell Engineering Building, Room 300N | Live office hours, starting August 30, 2023: Monday, 11:30am-12:30pm, and Wednesday, 10am-11am.

Location and time

Monday and Wednesday, 8:30--10am. Lectures start on Wednesday, August 30, 2023 and run officially until Monday, December 4, 2023. No lectures on October 9 and 11 (reading break). There won't be any lectures on Monday, September 4 (Labour Day), but there is an extra lecture on November 30, same place, same time.
We meet in McConnell 321 (the lounge). Course notes will be handed out in class.

Teaching Assistant

Max Dupre la Tour, McConnell Engineering 310/311. Email Max. Office hours: Tuesday and Thursday, 4-5pm.

Description

This course looks at basic methods for analyzing the average behavior of algorithms and data structures. It is shown how conventional and modern probability theoretical techniques can be used in this respect. The list of topics does not pretend to be exhaustive; rather, it is selected to give a broad horizontal view of possible applications. The students should be familiar with elementary concepts in probability theory and data structures.

Contents

Binary search trees Connection with the theory of records and random permutations.
Analysis of depth and height.
Quadtrees, k-d trees, union-find trees.
The uniform random recursive tree.
Preferential attachment trees.
Introduction to branching processes, branching random walks.

Conditional branching processes Analysis of simple families of random trees.
Galton-Watson trees.

Random graphs Simple random graph models, independent sets, coloring.
The second moment method.
Analysis of simple heuristics for graph problems.
The Erdös-Rényi theorem on connected graphs.
Random geometric graphs, the Gilbert disc model, percolation.

Randomized algorithms Introduction to the methodology.
Finding the k-th largest quickly on the average.
Randomized routing on networks.
Exponential large deviation inequalities.
Closest point problems.
Random incremental algorithms.
Randomzed approximation algorithms.

Combinatorial search problems Euclidean traveling salesman problem.
Assignment problems.
Martingales and the bounded differences method.
Concentration inequalities.

Markov chains Basic properties.
Markov chain Monte Carlo.
Generating random combinatorial objects.
Rapid mixing. Mixing time.

Entropy Entropy, coding and compression.
Entropy and random tries.
Digital search trees.

Evaluation

About nine sets of theoretical problems will be assigned.

Textbook

There is no specific textbook. Course notes will be handed out.

Selected references

Some references are given below.

N. Alon, J. Spencer, and P. Erdös, The Probabilistic Method, John Wiley, New York, 1992.
B. Bollobas, Random Graphs, Academic Press, New York, 1985.
L. Devroye, "Branching processes in the analysis of the heights of trees," Acta Informatica, vol. 24, pp. 277--298, 1987.
L. Devroye, "Applications of the theory of records in the study of random trees," Acta Informatica, vol. 26, pp. 123--130, 1988.
S. Janson, T. Luczak, A. Rucinski, Random Graphs, Wiley-Interscience, New York, 2000.
R. M. Karp, "The probabilistic analysis of some combinatorial search algorithms," in: Algorithms and Complexity, ed. J. F. Traub, pp. 1--19, Academic Press, New York, 1976.
R. M. Karp and J. M. Steele, "Probabilistic analysis of heuristics," in: The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, ed. E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan and D. B. Shmoys, pp. 181--205, John Wiley, New York, 1985.
D. E. Knuth, The Art of Computer Programming, Vol. 3 : Sorting and Searching, Addison-Wesley, Reading, Mass, 1973.
H. M. Mahmoud, Evolution of Random Search Trees, John Wiley, New York, 1992.
R. Motwani and P. Raghavan, Randomized Algorithms, Cambridge University Press, 1995.
E. M. Palmer, Graphical Evolution, John Wiley, New York, 1985.
J. Pearl, Heuristics. Intelligent Search Strategies for Computer Problem Solving (Chapter 5), Addison-Wesley, Reading, Mass, 1984.
W. Szpankowski, Average Case Analysis of Algorithms on Sequences, Springer-Verlag, New York, 2001.
J. S. Vitter and P. Flajolet, "Average-case analysis of algorithms and data structures," in: Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity, ed. J. van Leeuwen, pp. 431--524, MIT Press, Amsterdam, 1990.