Instructor: John Augustine

Slot "E" (Tue: 11 - 11:50, Wed: 10 - 10:50, Thu: 8 - 8.50, Fri: 16:50 - 17:40)

This will be a "virtual" course. I intend to deliver all lectures live via google meet. Recorded lecture video links are available below. You will need to sign in with your smail account in order to access it. All assessment will be through online means with submission through portals like turnitin that provide automated plagiarism checks.

You must have taken at least one algorithms course (either CS 2800 or CS 5800 or equivalent); this will be enforced. It will be good if you have take some university level probability course, but I will not require or enforce this.

This will be a mathematically intensive course with an emphasis on proving things rigorously. So mathematical maturity and aptitude towards rigorous proofs is a must.

There is no required textbook. The following references however may be quite useful.

• Randomized Algorithms, by Motwani and Raghavan. Cambridge University Press (1995). (Indian Edition is available and is worth purchasing.)

• Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis, by Mitzenmacher and Upfal. Cambridge University Press, 2nd edition (2017).

• Concentration of Measure for the Analysis of Randomized Algorithms, by Dubhashi and Panconesi. Cambridge University Press (2009).

• Randomized algorithms have been offered as a course at many universities across the world and many of them have excellent associated course notes. Here are a couple of sample course notes:

  • James Aspnes

  • Sariel Har-Peled

• In some situations, I may refer to specific resources that I list here.

  • Randomized Dictionary Structures by C. Pandu Rangan. Chapter in the Handbook of Data Structures and Applications. PDF.

This course will comprise five modules, each lasting about two weeks. Each module will have a core set of theoretical ideas that will be illustrated through algorithmic examples.

1. Fundamentals of Randomized Algorithms

   • Introduction to Probability Theory: Probability space, conditional probability, Bayes Theorem, Random Variables, Conditional Expectation, Probability Distributions, Markov's Inequality, Chebyshev's Inequality, Chernoff Bounds.

   • Probability ideas will be explained through algorithmic examples like Karger's MinCut, Quicksort, Randomized Selection, Parameter Estimation, and Randomized Permutation Routing.

2. Foiling the Adversary

   • The Paging Problem and Yao's minimax principle.

   • Adversarial Multi-Armed Bandit

   • Byzantine Agreement

This course will consist of five modules; see the overview of course contents above. Each module will have an associated assignment worth about five points, two recall-type short quizzes worth about five points, and a module test worth ten points.

All assessments will be done online with submissions through online means like turnitin that allow for plagiarism checks. Please academic honesty at all times. You can see my expectations here.