CSL857: Randomized Algorithms
II semester: 2012-13
Amitabha Bagchi
Class Timings: Tue Fri 2PM to 330PM.
Room: II 332.
Overview
Randomization has been a major tool in the design of algorithms for
some time now, and consequently the study of randomized algorithms has
developed in many directions. In this course we will not attempt to
comprehensively cover all the different directions, focussing instead
on beginning by putting our knowledge of probability theory on a more
rigorous foundation, then moving on to study Markov Chains with a view
to understanding the phenomenon of rapid mixing and its implications
for algorithms. Finally we will study the probabilistic method from an
algorithmic point of view. The focus of this course will be to build a
deep understanding of the topics covered and evaluation will be
through homework assignments and exams.
Textbooks and notes
-
Patrick Billingsley, Probability and Measure 3nd ed.,
Wiley, India (Indian Edition), 2008. Recommended purchase,
available in CSE library and Mail library.
- David
A. Levin, Yuval Peres, Elizabeth L. Wilmer, Markov Chains and
Mixing Times, AMS,
2008. Electronic version available.
- Venkatesan Guruswami, Rapidly Mixing Markov Chains: A
comparison of techniques, unpublished, 2000. Electronic
version available.
- Andrei Antonenko, Lecture notes for course on Linear Algebra, taught in 2003.
Lecture Schedule
The material to be covered in this course is divided into 12 units of
3 hours each. The source of the material is mentioned along with each
unit. Apart from these there are some additional units that will be
covered at times apart from regular lecture hours if there is
interest. The first 6 units are listed below for now. More will be
added later.
- Unit 1: Borel's normal number theorem and
Probability Measures. Source: Billingsley, Sections 1 and 2.
- Optional Unit: Existence and extension of
probability measures. Source: Billingsley, Section 3.
- Unit 2: General formulas, Independence,
Borel-Cantelli Lemmas. Source: Billingsley, Section 4.
- Unit 3: Simple random variables, expectations, the
law of large numbers. Source: Billingsley, Sections 5 and 6.
- Unit 4: Large deviations and the law of the
iterated logarith. Source: Billingsley, Section 9.
- Unit 5+6: Intro to finite Markov
chains and some examples of Markov chains. Source: Levin
et. al., Chapters 1, 2 and 3.
Homeworks
You will need to download the tex class file mts-hw.cls and keep it in the directory where you latex the homework file.
- Homework 1. Due by 24th January 2013, 11:59PM. Download pdf, tex source.
- Homework 2. Due by 22nd February 2013, 11:59PM. Download pdf, tex source.
- Homework 3. Due by 22nd March 2013, 11:59PM. Download pdf, tex source.
- Homework 4. Due by 12th April 2013, 11:59PM. Download pdf, tex source.
- Homework 5. Due by 22nd April 2013, 11:59PM. Download pdf, tex source.
- Homework 6. Due by 9th May 2013, 11:59PM. Download pdf, tex source.
Evaluation
TBA.
Amitabha
Bagchi