Syllabus

The course have 5 different modules as follows:

Module: Introduction

Instructor: Suman Kundu

Randomized algorithms, Universal Hash Family, Probabilistic Algorithm Analysis, Approximation Algorithms, $\epsilon$-Approximation Schemes, Sublinear time complexity, Sublinear Algorithms.

Module: Property Testing

Instructor: Suman Kundu

Testing list’s sortedness or monotonicity, Distribution testing, Testing properties of bounded degree graphs, Dense graphs and General graphs.

Module: Sketching and Streaming Algorithms

Instructor: Suman Kundu

Extremely Small-Space Data Structures, CountMin Sketch, Count Sketch, Turnstile Streaming, AMS Sketch, Graph Sketching, Graph Connectivity

Module: Map-Reduce

Instructor: Dr. Debasis Das

Map-Reduce Algorithms in Constrains Settings such as small memory, few machines, few rounds, and small total work, Efficient Parallel Algorithms

Module: External memory and Cache-Obliviousness

Instructor: Dr. Debasis Das

Minimizing I/O for large datasets, Algorithms and data structures such as B-trees, Buffer trees, Multiway merge sort