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)