Objectives:
To introduce the power of randomization in the design and analysis of algorithms.
Course Contents:
Brief introduction to probability theory including basic tail bounds.
Brief overview of randomized algorithms: Paradigms for randomized algorithms like randomized attrition, randomized
incremental algorithms along with backward analysis, foiling the adversary, random sampling, establishing an abundance of
witnesses, hashing, and probabilistic methods along with some illustrative examples. Monte Carlo algorithms exemplified by
Karger's min-cut and randomized primality testing; Las Vegas algorithms exemplified by quicksort, selection, and binary
planar partitions.
Randomized Data Structures: Random Treaps, Skip Lists, Hash Tables, Universal Family of Hash Functions, Perfect Hashing.
Randomized Computational Geometry: Illustrations of randomized incremental algorithms like randomized convex hull
construction, geometric duality, half space intersections, Delaunay Triangulation, trapezoidal decomposition; illustrations of
random sampling like point location in arrangements, and linear programming.
Online algorithms: Adversary models, online paging against oblivious and adaptive adversaries, Yao's minimax principle,
lower bound for online paging against an oblivious adversary, the k-server problem.
Distributed algorithms: Symmetry breaking problems like leader election, Byzantine agreement, maximal independent set, and colouring; algorithms for dynamic networks; the k-machine model for processing large graphs.
Streaming algorithms: the streaming model, approximate counting, reservoir sampling, AMS sketching.
Property testing algorithms: the property testing model, testing whether a graph is connected, bipartite (enforce and test paradigm), and triangle free (using Szemeredi's regularity lemma).
Text Books:
- Randomized Algorithms, by Motwani and Raghavan, Cambridge University Press, 1995.
- Probability and Computing: Randomized Algorithms and Probabilistic Analysis, by Mitzenmacher and Upfal, Cambridge
University Press, 2nd edition, 2017.
Reference Books:
- Computational Geometry: Algorithms and Applications, by Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark
Overmars, 3rd edition, Springer-Verlag, 2008.
- Algorithmic and Analysis Techniques in Property Testing, by Dana Ron. Found. Trends Theor. Comput. Sci. 5, 2 (February
2010), 73-205.
- Mining of Massive Datasets, by Leskovec, Rajaraman, and Ullman, available at http://www.mmds.org.
