Randomized Algorithms
Sep - Dec, 2020
IIT Madras
Australian captain Don Bradman (left) and England captain Gubby Allen toss at the start of the 1936–37 Ashes series.
Embedded Files
Modern computer algorithms rely heavily on random decisions. Such randomized algorithms are often preferred over deterministic algorithms due to their simplicity, elegance, and efficiency. In fact, problems in some computational models cannot even be solved without randomization. This course will introduce you to randomized algorithms and teach you how to design and analyze them.
Organizational Details
Organizational Details
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.
Prerequisites
Prerequisites
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.
Reference Books
Reference Books
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:
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.
Course Contents
Course Contents
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.
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.
Foiling the Adversary
The Paging Problem and Yao's minimax principle.
Adversarial Multi-Armed Bandit
Byzantine Agreement
Grading Scheme
Grading Scheme
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.
Page updated
Report abuse