| 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, query model and if time permits, 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 Structures courses and have some knowledge of elementary discrete probability. The course "Topics in Algorithms and Complexity" is desirable.
| Taught by: Arjit Bishnu (ArB) |
Class Timings: | Tuesday 16:00-18:00, Friday 14:00-16:00 ACMU seminar room (6th floor, Platinum Jubilee Building) |
| 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 (21-01-20) |
Introduction to Sub-linear algorithms --
Read from (W1)-(W3) and (B2)
Folklore majority finding algorithm, Frequency estimation (Misra-Gries algorithm) --
Read from (W2) |
-- |
| Lecture 2 (24-01-20) |
Approximate counting: Morris's algorithm; initial technique of Variance minimization by taking the average of multiple instances;
Read from (W1)
Initial ideas of distinct elements --
Read from (B1) |
-- |
| Lecture 3 (28-01-20) |
Vitter's reservoir sampling --
Read from (W4)
Finding distinct elements and initial ideas of use of hashing --
Read from (B1) |
-- |
| Lecture 4 (04-02-20) |
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 5 (06-02-20) |
Idea on streaming models like vanilla, cash register, turnstile, etc. and sketching --
Read from (W2)
Heavy hitters and count min sketch --
Read from (W4) and (W2) |
-- |
| Lecture 6 (07-02-20) |
Count sketch --
Read from (W2) |
-- |
| Lecture 7 (11-02-20) |
Estimating the number of distinct elements: a constant multiplicative error algorithm |
-- |
| Lecture 8 (14-02-20) |
Estimating the number of distinct elements: an (epsilon, delta) algorithm |
-- |
| Lecture 9 (18-02-20) |
AMS tug-of-war sketch for F_2; |
-- |
| Lecture 10 (25-02-20) |
A geometric interpretation (on dimensionality reduction) of AMS Tug-of-war sketch: |
-- |
| Lecture 11 (28-02-20) |
Introduction to (one-way) communication complexity: EQUALITY (EQ), INDEX, DISJOINTNESS (DISJ) |
-- |
| Lecture 12 (13-02-20) |
A brief discussion on reductions; |
-- |