NPTEL : NOC:Algorithms for Big Data (Computer Science and Engineering)

Co-ordinators : Prof. John Augustine


Lecture 1 - Basic definitions

Lecture 2 - Conditional probability

Lecture 3 - Example problems

Lecture 4 - Karger's mincut algorithm

Lecture 5 - Analysis of Karger's mincut algorithm

Lecture 6 - Random variables

Lecture 7 - Randomized quicksort

Lecture 8 - Problem solving video - The rich get richer

Lecture 9 - Problem solving video - Monty Hall problem

Lecture 10 - Bernoulli, Binomial and Geometric distributions

Lecture 11 - Tail Bounds

Lecture 12 - Application of Chernoff bound

Lecture 13 - Application of Chebyshev's inequality

Lecture 14 - Intro to Big Data Algorithms

Lecture 15 - SAT Problem

Lecture 16 - Classification of States

Lecture 17 - Stationary Distribution of a Markov Chain

Lecture 18 - Celebrities Case Study

Lecture 19 - Random Walks on Undirected Graphs

Lecture 20 - Intro to Streaming, Morris Algorithm

Lecture 21 - Reservoir Sampling

Lecture 22 - Approximate Median

Lecture 23 - Overview

Lecture 24 - Balls, bins, hashing

Lecture 25 - Chain hashing, SUHA, Power of Two choices

Lecture 26 - Bloom filter

Lecture 27 - Pairwise independence

Lecture 28 - Estimating expectation of continuous function

Lecture 29 - Universal hash functions

Lecture 30 - Perfect hashing

Lecture 31 - Count-min filter for heavy hitters in data streams

Lecture 32 - Problem solving video - Doubly Stochastic Transition Matrix

Lecture 33 - Problem solving video - Random Walks on Linear Structures

Lecture 34 - Problem solving video - Lollipop Graph

Lecture 35 - Problem solving video - Cat And Mouse

Lecture 36 - Estimating frequency moments

Lecture 37 - Property testing framework

Lecture 38 - Testing Connectivity

Lecture 39 - Enforce and Test Introduction

Lecture 40 - Testing if a graph is a biclique

Lecture 41 - Testing bipartiteness

Lecture 42 - Property testing and random walk algorithms

Lecture 43 - Testing if a graph is bipartite (using random walks)

Lecture 44 - Graph streaming algorithms: Introduction

Lecture 45 - Graph streaming algorithms: Matching

Lecture 46 - Graph streaming algorithms: Graph sparsification

Lecture 47 - MapReduce

Lecture 48 - K-Machine Model (aka Pregel Model)