| 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 |
| 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 (04-01-13) |
Introduction, Expected number of updations in finding minimum Waiting for the first success and quicksort |
- | (B1), (W2) |
| Lecture 2 (08-01-13) |
Linearity of expectation, Conditional probability and Graph min-cut |
- | (B1), (B3) |
| Lecture 3 (10-01-13) |
Low dimensional linear programming | - | (W2) |
| Lecture 4 (11-01-13) |
Minimum Enclosing Disc | - | (W2) |
| Lecture 5 (12-01-13) |
Randomized approximation algorithm for MAX 3-SAT | - | (B1) |
| Lecture 6 (15-01-13) |
Lower bound on crossing number: A proof using elementary probability |
- | - |
| Lecture 7 (17-01-13) |
Universal hash functions | - | (B1), (B3) |
| Lecture 8 (18-01-13) |
Universal hash function; Closest pair of points |
- | (B1), (B3) |
| Lecture 9 (29-01-13) |
Closest pair of points; Occupancy problems |
- | (B1), (B2), (B3) |
| Lecture 10 (01-02-13) |
Markov's and Chebyshev's inequality |
- | (B1), (B2), (B3) |
| (28-02-13) | Mid Semestral examination |
Model Solution |
-- |
| Lecture 11 (08-03-13) |
Randomized Selection | -- | (B2), (B3), (W1) |
| Lecture 12 (12-03-13) |
Chernoff bounds | - | (B1), (B2), (B3), (W1) |
| Lecture 13 (15-03-13) |
Chernoff bounds, Load balancing | - | (B1), (B2), (B3) |
| Lecture 14 (19-03-13) |
Chernoff bounds, Packet routing | - | (B1), (B2), (B3) |
| Lecture 15 (22-03-13) |
Packet Routing | - | (B1), (B2), (B3) |
| Lecture 16 (26-03-13) |
Randomized Incremental Construction:
Convex Hull |
- | (B3), (B5) |
| Lecture 17 (01-04-13) |
Randomized Incremental Construction:
Trapezoidal Decomposition |
- | (B3), (B5) |
| Lecture 18 (02-04-13) |
Skip Lists | - | (B3), (B5) |
| Lecture 19 (05-04-13) |
Probabilistic Methods | - | (B2), (B3) |
| Lecture 20 (09-04-13) |
Probabilistic Methods | - | (B2), (B3) |
| Lecture 21 (10-04-13) |
Probabilistic Methods: Lovasz Local Lemma | - | (B2), (B3) |
| Lecture 22 (12-04-13) |
Probabilistic Methods: Lovasz Local Lemma | - | (B2), (B3) |
| Lecture 23 (13-04-13) |
Random Graphs | - | (W3), (B2), (B3) |
| Lecture 24 (13-04-13) |
Random Graphs | - | (W3), (B2), (B3) |
| Lecture 23 (13-04-13) |
Random Graphs | - | (W3), (B2), (B3) |