| 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 9:25-11:10, Thursday 9:25-11:10 |
| 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 |
| 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 | EXERCISE |
| Lecture 1 (05-10-21) |
Introduction to Sub-linear algorithms --
Read from (W1)-(W3) and (B2)
Folklore majority finding algorithm
Read from (W2) |
-- |
| Lecture 2 (07-10-21) |
Introduction to data streaming and its models;
Read from (W1) and (W2) |
-- |
| Lecture 3 (21-10-21) |
Introduction to data streaming and its models;
Read from (W1) and (W2)
Folklore majority finding algorithm, Frequency estimation (Misra-Gries algorithm) --
Read from (W2) |
-- |
| Lecture 4 (26-10-21) |
Approximate counting: Morris's algorithm; initial technique of Variance minimization by taking the average of multiple instances;
Read from (W1) |
-- |
| Lecture 5 (28-10-21) |
Finding distinct elements and initial ideas of use of hashing --
Read from (B1) |
-- |
| Lecture 6 (02-11-21) |
Some ideas on hashing --
Read from (B1) and (W3)
Using the median trick on Morris to boost up success probability --
Read from (W1) and (W2) |
-- |
| Lecture 7 (09-11-21) |
Vitter's reservoir sampling --
Read from (W4) |
-- |
| Lecture 8 (11-11-21) |
Approximate Heavy hitters and count min sketch --
Read from (W4) and (W2) |
-- |
| Lecture 9 (16-11-21) |
Approximate Heavy hitters and count min sketch --
Read from (W4) and (W2) |
-- |
| Lecture 10 (23-11-21) |
Approximate heavy hitters and Count sketch --
Read from (W2) |
-- |
| Lecture 11 (25-11-21) |
Count sketch (contd.)--
Read from (W2) |
-- |