CS6170 - Randomized Algorithms

Course Data :


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:

  1. Randomized Algorithms, by Motwani and Raghavan, Cambridge University Press, 1995.
  2. Probability and Computing: Randomized Algorithms and Probabilistic Analysis, by Mitzenmacher and Upfal, Cambridge University Press, 2nd edition, 2017.

Reference Books:

  1. Computational Geometry: Algorithms and Applications, by Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars, 3rd edition, Springer-Verlag, 2008.
  2. Algorithmic and Analysis Techniques in Property Testing, by Dana Ron. Found. Trends Theor. Comput. Sci. 5, 2 (February 2010), 73-205.
  3. Mining of Massive Datasets, by Leskovec, Rajaraman, and Ullman, available at http://www.mmds.org.




Credits Type Date of Introduction
4-0-0-0-0-8-12 Elective Nov 2017

Previous Instances of the Course

© 2016 - All Rights Reserved - Dept of CSE, IIT Madras
Website Credits