| Course Outline | General Information | Study Material | Lectures (classwise) |
The course consists of 4 lecture hours per week.
The basic thrust of the course would be to study Randomization techniques and algorithms and some randomized complexity classes.
We will try to stick to the basic course outline as given in this page, but may deviate a bit.
We would assume in this course that you have undergone the Data and File Structures, Design and Analysis of Algorithms and Discrete Structures courses and have some knowledge of elementary discrete probability.
| Class Timings: |
| Books |
(B1) Algorithm Design J. Kleinberg and Eva Tardos Pearson Education (B2) Probability and Computing: Randomized Algorithms and Probabilistic Analysis Michael Mitzenmacher and Eli Upfal Cambridge (B3) Randomized Algorithms Rajeev Motwani and Prabhakar Raghavan Cambridge (B4) Computational Geometry: Algorithms and Applications Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars Springer Verlag (B5) Computational Geometry: An Introduction Through Randomized Algorithms Ketan Mulmuley Prentice Hall (B6) The Probabilistic Method Noga Alon, Joel H. Spencer Wiley (B7) Geometric Approximation Algorithms Sariel Har-Peled American Mathematical Society |
| Web Resources |
(W1) Lecture Notes by Sariel Har Peled
(W2) Lecture Notes by David Mount (W3) Chapter on Random Graphs (Hopcroft and Kannan's draft) |
| LECTURE DATES | TOPICS | NOTES (pdf) | BOOKS |
| Lecture 1 (07-01-14) |
Introduction, Linearity of expectation,
Waiting for the first success and its applications -- coupon collector's problem, quicksort, selection |
- | (B1) |
| Lecture 2 (09-01-14) |
Randomized approximation algorithm for MAX 3SAT | - | (B1) |
| Lecture 3 (16-01-14) |
Conditional probability and graph min-cut; lower bound on crossing number: a proof using elementary probability |
- | (B1), (W1) |
| Lecture 4 (21-01-14) |
Backward analysis -- low dimensional LP, Minimum enclosing disc |
- | (B4), (W2) |
| Lecture 5 (23-01-14) |
Universal hash functions | - | (B1), (B3) |
| Lecture 6 (28-01-14) |
Randomized algorithm for closest pair of points using universal hashing |
- | (B1) |
| Lecture 7 (30-01-14) |
Markov's and Chebyshev's inequality |
- | (B1), (B2), (B3) |
| Lecture 8 (31-01-14) |
Randomized Selection: an application of Chebyshev's inequality |
-- | (B2), (B3), (W1) |
| Lecture 9 (05-02-14) |
Chernoff Bounds | - | (B1), (B2), (B3) |
| Lecture 10 (12-02-14) |
Chernoff Bounds | - | (B1), (B2), (B3) |
| Lecture 11 (21-02-14) |
Packet routing | - | (B1), (B2), (B3) |
| Lecture 12 (06-03-14) |
Probabilistic Methods | - | (B2), (B3), (B6) |
| Lecture 13 (07-03-14) |
Probabilistic Methods | - | (B2), (B3), (B6) |
| Lecture 14 (20-03-14) |
Probabilistic Methods | - | (B2), (B3), (B6) |
| Lecture 15 (24-03-14) |
Random Graphs | - | (W3), (B2), (B3) |
| Lecture 16 (25-03-14) |
Random Graphs | - | (W3), (B2), (B3) |
| Lecture 17 (26-03-14) |
Random Graphs | - | (W3), (B2), (B3) |
| Lecture 18 (27-03-14) |
Skip List | - | (B3), (B5) |
| Lecture 19 (01-04-14) |
Skip List | - | (B3), (B5) |
| Lecture 20 (03-04-14) |
Lovasz Local Lemma | - | (B2), (B3) |
| Lecture 21 (04-04-14) |
Lovasz Local Lemma | - | (B2), (B3) |
| Lecture 22 (08-04-14) |
VC-dimension, epsilon net | - | (B2), (B3), (B6), (B7), (W1) |
| Lecture 23 (10-04-14) |
VC-dimension, epsilon net | - | (B2), (B3), (B6), (B7), (W1) |
| Lecture 24 (15-04-14) |
VC-dimension, epsilon net | - | (B2), (B3), (B6), (B7), (W1) |
| Lecture 25 (17-04-14) |
VC-dimension, epsilon net | - | (B2), (B3), (B6), (B7), (W1) |