| Lecture hours: |
|
Mon 14:00 -- 15:25 and Thu 14:00 -- 15:25
|
| Office hours: |
|
Wed 11:00 -- 12:30
|
| Location: |
|
SIC 201
|
| Instructor: |
|
Nutan Limaye
(firstname[AT]cse[DOT]iitb[DOT]ac[DOT]in)
|
Course Outline
The course outline is sketched out
here.
Lecture notes
The course is divided into 4 modules.
Algorithms for problems on large datasets
Math Preliminaries
[pdf]
Lecture 1: Introduction
[pdf]
Lecture 2: Computing the length of the input (Morris's algorithm)
[pdf]
Lecture 3: Counting the number of distinct elements.
[pdf]
Lecture 4: Pairwise independence
[pdf]
Lecture 5: Frequency moments and computation of F2
[pdf]
Lecture 6: Count-min and count sketches.
[pdf]
Lecture 7: Analysis of Count sketch algorithm.
[pdf]
Lecture 8: Sampling based approach for distinct elements.
[pdf]
Algorithms for problems in linear algebra/geometry
Lecture 9: A brief introduction to Johnson-Linderstrauss Lemma and its versions.
[pdf]
Algorithms for large graphs
Information theory for proving lower bounds
Notes will be uploaded soon.
Tutorials, Quizes, and Exams
Will be updated soon.
The style file used for scribe notes is borrowed from Prahladh Harsha.