| 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. Towards the end of the course, Prof. Susmita Sur-Kolay will deliver some lectures on quantum computation.
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.
| Class Timings: | Wednesday 11:45-13:30, Friday 16:15-17:55 Room No. 719, S. N. Bose Bhavan (Library Building) |
| The necessary evil - marks, exam, etc.: | Mid-sem: 30, End-sem: 50, Internal evaluation: 20 |
| 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 |
| Web Resources |
(W1) Lecture Notes by Sariel Har Peled
(W2) Lecture Notes by David Mount |
| LECTURE DATES | TOPICS | NOTES (pdf) | BOOKS |
| Lecture 1 (04-01-12) |
Introduction, Expected number of updations in finding minimum |
- | (B1), (W1) |
| Lecture 2 (18-01-12) |
Graph min-cut, selection, quicksort |
- | (B1), (W1) |
| Lecture 3 (20-01-12) |
Linearity of Expectation and its applications | - | (B1) |
| Lecture 4 (23-01-12) |
Randomized approximation for Max 3-SAT | - | (B1) |
| Lecture 5 (25-01-12) |
Backward Analysis: low dimensional linear programming, minimum enclosing disk |
- | (B4), (W2) |
| Lecture 6 (27-01-12) |
Closest pair of points | - | (B1), (W1) |
| Lecture 7 (01-02-12) |
Universal hash functions | - | (B1), (B3), (W1) |
| Lecture 8 (06-02-12) |
Universal hash functions; Occupancy Problems |
- | (B1), (B3), (W1) |
| Lecture 9 (07-03-12) |
Occupancy Problems; Markov's and Chebyshev's inequality |
- | (B1), (B2), (B3) |
| Lecture 10 (12-03-12) |
Randomized Selection: An application of Chebyshev's inequality |
- | (B3) |
| Lecture 11 (14-03-12) |
Chernoff bounds | - | (B1), (B3) |
| Lecture 12 (16-03-12) |
Randomized selection, Load balancing | - | (B1), (B3) |
| Lecture 13 (19-03-12) |
Packet Routing | - | (B1), (B3) |
| Lecture 14 (21-03-12) |
Skip List | - | (B3) |
| Lecture 15 (23-03-12) |
Convex Hull | - | (B3) |