| 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 sublinear algorithms, specifically streaming, and property testing.
We will try to stick to the basic course outline as given here.
We would assume in this course that you have undergone the Data and File Structures, Design and Analysis of Algorithms and Discrete Mathematics courses and have some knowledge of elementary discrete probability. The course "Randomized and Approximation Algorithms" is desirable.
| Taught by: Arjit Bishnu (ArB) and Arijit Ghosh (ArG) |
Class Timings: | Tuesday 14:15-16:00, Thursday 16:00-18:00 |
| The necessary evil - marks, exam, etc.: | Mid-sem: 20, End-sem: 50, Internal evaluation: 30 |
| Books |
(B1) Foundations of Data Science A. Blum, J. Hopcroft and R. Kannan Cambridge University Press (B2) Design and Analysis of Algorithms: A Contemporary Perspective S. Sen and A. Kumar Cambridge University Press (B3) Introduction to Property Testing Oded Goldreich Cambridge University Press (B4) The Probabilistic Method Noga Alon, Joel H. Spencer 4th edition, Wiley (B5) Algorithm Design J. Kleinberg and Eva Tardos Pearson Education (Indian edition) (B6) Algorithms S. Dasgupta, C. Papadimitriou and U. Vazirani Tata McGraw-Hill (B7) Probability and Computing: Randomized Algorithms and Probabilistic Analysis M. Mitzenmacher and E. Upfal Cambridge University Press |
| Web Resources |
(W1) Lecture Notes by Jelani Nelson
(W2) Lecture Notes by Amit Chakrabarti (W3) Lecture Notes by Paul Beame (W4) Lecture Notes by Tim Roughgarden on "Modern Algorithmic Toolbox" (with Greg Valiant) (W5) Lecture Notes by Tim Roughgarden on Communication Complexity (for Algorithm Designers) (W6) Lecture Notes on Randomized Algorithms by Sariel Har-Peled |
| LECTURE DATES (Taught by) | TOPICS | SCRIBE |
| Lecture 1 (22-07-25) |
Introduction to model centric algorithms, streaming, graph streaming models --
Read from (B1), (B2) and (W2)
Folklore majority finding algorithm
Read from (W2) |
-- |
| Lecture 2 (24-07-25) |
Finding frequent items deterministically: Misra-Gries; |
-- |
| Lecture 3 (31-07-24) |
Concentration inequalities for randomized quicksort;
Read from (W6)
Reservoir Sampling --
Read from (W4) |
-- |
| Lecture 4 (05-08-25) |
Basics of k-universal hashing;
Read from (W6), (W2) and (W4)
Finding the number of distinct elements;
Read from (B1) |
-- |
| Lecture 5 (12-08-25) |
Approximate Counting (MORRIS); Idea of independent trials and median of means;
Read from (W1) and (W2) |
-- |
| Lecture 6 (14-08-25) |
Frequency Moment estimation F_2 (AMS sketch);
Read from (W1) and (W2) |
-- |
| Lecture 7 (21-08-25) |
Frequency Moment estimation F_k (AMS sketch);
Read from (W1) and (W2) |
-- |
| Lecture 8 (26-08-25) |
Count sketch and Count-Min Sketch; epsilon heavy hitter;
Read from (W2) and (W4) |
-- |
| Lecture 9 (30-08-25) |
Ideas of Johnson Lindenstrauss lemma;
Read from (B1) and (W4)
Number of distinct elements;
Read from (W2) |