CS6170 Randomized Algorithms

Jan - May 2025

about

Whenever you’re called on to make up your mind,
and you’re hampered by not having any,
the best way to solve the dilemma, you’ll find,
is simply by spinning a penny.

No - not so that chance shall decide the affair
while you’re passively standing there moping;
but the moment the penny is up in the air,
you suddenly know what you’re hoping.

                              - Piet Hein

Coordinates

• Where: SSB 134
• When: F slot - Tue (5 pm), Wed (11 am), Thu (9 am), Fri (8 am)

Instructor

• Yadu Vasudev
• SSB 207
• yadu@cse.iitm.ac.in

TA

• Dhruv Aggarwal (cs21b024@smail)

Important links

• Moodle
• Ed Discussions (for discussions, Q/A, announcements)
  Join using your smail/iitm ids via this link
• Anonymous course feedback

Course calendar

contents

About this course

This is an introductory course on design and analysis of randomized algorithms. Randomization is ubiquitous in computer science, and this course introduces some computatational problem where randomization gives efficient and elegant solutions. We will also learn how to think about randomized algorithms and the tools required 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.

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 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 minimizes 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 - How easy is it to approximate the size of a set if you know how to sample a random element in the set efficiently?
• 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.

administrivia

Weekly schedule

There will be four lectures every week, some of which will be converted to tutorial/problem-solving sessions. You can also use the course discussion forum to discuss these with your peers and the course staff.

---

Grading policy (tentative)

• Problem sets (1*5 + 3*10) = 35%
• Course project (in groups of at most 3) = 15%
• Mid-semester exam = 20%
• End-semester exam = 30%

---

Important dates (tentative)

• Problem sets (release dates): Jan 31, Feb 21, Mar 14, Apr 11
• Mid-semester exam: Mar 4
• End-semester: May 14 (according to institute calendar)

The dates and details of the course project will be announced after about a month of the start of the classes.

Communication

Please sign up on the course discussion forum here. This will be the first point of contact for any issues related to the course. For general questions related to the course (any comments/doubts), please create a thread in the correct category and add your question/comment there. You are encouraged to reply and clear the doubts of your friends. To encourage this interaction, the forum supports anonymous posts and answers. Please be courteous to others when you are posting anonymously.

lectures