Computer Science 690
Probabilistic Analysis of Algorithms and Data Structures
August 23, 2021

Fall 2021 --- Course Syllabus





Instructor  


Luc Devroye | Email | McConnell Engineering Building, Room 300N | Live office hours: Wednesday, 11:30am-12:30pm and Friday, 10-11am (except Friday September 10). Outside on the lower campus.


Location and time  


Wednesday, Friday 8:30--10am. Lectures start on Wednesday, September 1, 2021 and run officially until Friday, December 3, 2021. The December 1 and December 3 lectures are moved to November 1 and 15, respectively, same place, same time.

We meet in McConnell 103. Course notes will be handed out in class.

A bit of what happened between March 2020 and August 2021: Realizing that live lectures are far superior to virtual lectures (for clarity, feedback, mental health, entertainment, blood pressure and social happiness), and that outdoor spaces beat indoor spaces in our fight against the spread of covfefe, I asked McGill's politburo for permission to hold live lectures under an open tent or canopy on the lower campus. The proposal was approved at all levels (with thanks to the School of Computer Science and the Faculty of Science) and then cold-bloodedly killed by the central Kommandatur---an obscure committee called the EOC (Emergency Operations Centre). A request to teach outdoors in 2021 without a tent was also declined. We are forced to teach inside and McGill University insists that unvaccinated students should be allowed to mingle with the rest, a decision that is medically ill-advised, legally troublesome, and ethically corrupt. [Those responsible for that decision include Christopher Manfredi, Christopher Buddle and Fabrice Labeau.] I will teach, but I will ask the students to please please please be careful and mindful.


Teaching Assistant


Marcel Goh, McConnell Engineering 310/311. Office hours: 1:30-2:30, Tuesday and Thursday. The Tuesday session will be by Zoom (link will be sent by email). The Thursday session will be live in his lab/office (310/311). Email Marcel Goh.


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.
Analysis of depth and height.
Quadtrees, k-d trees, union-find trees.
Introduction to branching processes, branching random walks.
Divide-and-conquer Expected time analysis of divide-and-conquer methods.
Algorithms for outer layers and convex hulls.
Analysis of the cardinality of the random convex hull.
Randomized algorithms Introduction to the methodology.
Finding the k-th largest quickly on the average.
Exponential large deviation inequalities.
Closest point problems.
Random incremental algorithms.
Randomzed approximation algorithms.
Conditional branching processes Analysis of simple families of random trees.
Random graphs Random graphs, independent sets, coloring.
The second moment method.
Analysis of simple heuristics for graph problems.
Linear expected time connectivity algorithm.
Properties of sparse random graphs.
The Erdös-Rényi theorem on connected graphs.
Random geometric graphs, the Gilbert disc model, percolation.
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.
Random walks Random walks for analyzing trees.
Bin packing heuristics.
Hashing, bucketing Analysis of various hashing algorithms.
Influence of non-uniform distributions.
Maximal occupancy.
Paradigm of two choices.


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 of the course material is based upon parts of the following references.

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.