# 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