| 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) |
Class Timings: | Tuesday 14:15-16:00, Thursday 14:15-16:00 |
| The necessary evil - marks, exam, etc.: | Mid-sem: 10, End-sem: 50, Internal evaluation: 40 |
| 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) |
| LECTURE DATES (Taught by) | TOPICS | SCRIBE |
| Lecture 1 (02-08-22) |
Introduction to model centric algorithms, reduction --
Read from (B5) and (B6)
Folklore majority finding algorithm
Read from (W2) |
-- |
| Lecture 2 (04-08-22) |
Introduction to randomized algorithms -- quicksort, median finding, minimum cut;
Read from (B5), (B6) and (B7) |
-- |
| Lecture 3 (16-08-22) |
Introduction to Universal Hashing;
Read from (B5), (B6) and (W4)
Introduction to Markov and Chebyshev's inequality --
Read from (B5) and (B6) |
-- |
| Lecture 4 (17-08-22) |
Introduction to Chernoff bounds;
Read from (B7) |
-- |
| Lecture 5 (22-08-22) |
Applications of Chernoff bounds: load balancing and packet routing;
Read from (B7) |
-- |
| Lecture 6 (23-08-22) |
Streaming models; Misra Gries
Read from (W1) and (W2) |
-- |
| Lecture 7 (25-08-22) |
Approximate counting: Morris and its variants; Using the median of means trick;
Read from (W1) and (W2) |
-- |
| Lecture 8 (29-08-22) |
Hashing (revision). Number of distinct elements;
Read from (B1) |
-- |
| Lecture 9 (30-08-22) |
Number of distinct elements;
Read from (W2) |
-- |
| Lecture 10 (06-09-22) |
Reservoir sampling;
Read from (W4) |
-- |
| Lecture 11 (08-09-22) |
Approximate heavy hitters: Count Min Sketch;
Read from (W4) |
-- |
| Lecture 12 (12-09-22) |
Approximate Heavy Hitters: Count Sketch;
Read from (W2) |
-- |
| Lecture 13 (13-09-22) |
Frequency moments: AMS sketch for F_2;
Read from (W2) |
-- |
| Lecture 14 (27-09-22) |
Geometric interpretation of AMS Tug-of-War Sketch; The AMS estimator of F_k;
Read from (W2) |
-- |
| Lecture 15 (29-09-22) |
Communication complexity, Results on EQ, INDEX and DISJ, Connection to streaming lower bounds;
Read from (W2) |
-- |
| Lecture 16 (10-10-22) |
Graph Streaming Algorithms: Connectedness, Bipartiteness, Shortest path; Distance estimation via spanners;
Read from (W2) |
-- |
| Lecture 17 (11-10-22) |
Graph Streaming Algorithms: Proof of the algorithms for spanners, maximum cardinality matching;
Read from (W2) |
-- |
| Lecture 18 (13-10-22) |
Maximum Weight Matching;
Read from (W2) |
-- |
| Lecture 18 (13-10-22) |
Maximum Weight Matching;
Read from (W2) |
-- |
| Lecture 19 (17-10-22) |
Rectangle property of deterministic communication protocols, Transcript, Lower bound for EQ, Randomized lower bounds: F_infty;
Read from (W5) and (W2) |
-- |
| Lecture 20 (18-10-22) |
Distinct elements lower bound, Graph connectedness lower bound, Multipass streaming lower bound;
Read from (W2) |
-- |
| Lecture 21 (20-10-22) |
Randomized lower bounds: Yao's minimax method;
Read from (xx) |
-- |
| Lecture 22 (31-10-22) |
Computing F_k for any k between 0 and 2;
Read from (W2) |
-- |
| Lecture 23 (01-11-22) |
Analysis of computing F_k for any k between 0 and 2 -- Continued;
Read from (W2) |
-- |
| Lecture 24 (03-11-22) |
Compressed sensing: Sparse recovery from 1-sparse vector;
Read from (W2) |
-- |
| Lecture 25 (07-11-22) |
Map Reduce (lecture by Debapriyo Majumdar);
Read from slides to be supplied |
-- |
| Lecture 26 (08-11-22) |
Clustering over metric space: 8-factor approximation of metric k-center problem ;
Read from (W2) |
-- |
| Lecture 27 (10-11-22) |
Map Reduce, Hadoop (lecture by Debapriyo Majumdar);
Read from slides |
-- |
| Lecture 28 (11-11-22) |
(1+\epsilon) estimator of minimum enclosing ball using coresets and theta-grid;
Read from (W2) |
-- |
| Lecture 29 (14-11-22) |
Weight based sampling: l_0 sampling;
Read from (W2) |
-- |
| Lecture 30 (15-11-22 and 22-11-22) |
Query complexity: estimating the average degree of a graph whose vertex set is only known;
Read from the original paper by Goldreich and Ron |
-- |