About this course

This course is an introductory course in the design and analysis of randomized algorithms. Randomization is unavoidable when studying many computational tasks, and this course aims to equip you with the necessary ideas to design randomized algorithms, and the tools and techniques to analyze such algorithms.

Prerequisites: A course in design and analysis of algorithms, and basic discrete probability will be useful. The way you think about designing algorithms will be quite different from what you saw in the undergrad algorithms course since the emphasis is not on designing algorithms that are always correct, but ones that are correct most of the time. For most of the course, you will only require discrete probability. Starting from the basics, we will build the probabilistic tools that are necessary to understand randomized algorithms.

The course will require you to design algorithms, and then mathematically prove their correctness. There will not be any programming component for this course.

---

Course contents

The course will look at the following content in detail. The order of the topics covered may vary:

• Simple randomized algorithms and their analysis - In this part we will recall some basic discrete probability while analyzing algorithmic questions.
• Concentration inequalities - We will look at concentration inequalities (Chernoff-Hoeffding) and their application in analyzing randomized algorithms.
• Balls-in-bins and hashing - We will see data structures for dictionaries in detail and ways to analyze their performance.
• Online algorithms - How do you design a caching mechanism that minimized page faults? Can you do as good as when you have the power of hindsight?
• Markov chains and random walks - How long will you take to reach your destination if you choose to board a random bus at every bus stop?
• Markov chain Monte-Carlo
• VC dimension and PAC learning, algebraic techniques (if time permits)

---

Course resources

Our main sources of reference will be the following textbooks.

1. Probability and Computing (Michael Mitzenmacher and Eli Upfal)
2. Randomized Algorithms (Rajeev Motwani and Prabhakar Raghavan)

Apart from this, there are a lot of resources available online. We may refer to them occasionally. Both the books contain a number of exercise problems for practice. This course was offered in July-Nov 2021 and July-Nov 2022.