Learn · NPTEL

Course10610614248 lectures

Algorithms for Big Data

Prof. John Augustine · IIT Madras

Start with lecture 1 At NPTEL

Lectures

Week 1

  1. Lesson 1 - Basic definitions Video
  2. Lesson 2 - Conditional probability Video
  3. Lesson 3 - Example problems Video
  4. Lesson 4 - Karger's mincut algorithm Video
  5. Lesson 5 - Analysis of Karger's mincut algorithm Video
  6. Lesson 6 - Random variables Video
  7. Lesson 7 - Randomized quicksort Video
  8. Problem solving video - The rich get richer Video
  9. Problem solving video - Monty Hall problem Video

Week 2

  1. Lesson 1 - Bernoulli, Binomial, and Geometric distributions Video
  2. Lesson 2 - Tail Bounds Video
  3. Lesson 3 - Application of Chernoff bound Video
  4. Lesson 4 - Application of Chebyshev's inequality Video

Week 3

  1. Lesson 1 - Intro to Big Data Algorithms Video
  2. Lesson 2 - SAT Problem Video
  3. Lesson 3 - Classification of States Video
  4. Lesson 4 - Stationary Distribution of a Markov Chain Video
  5. Lesson 5 - Celebrities Case Study Video
  6. Lesson 6 - Random Walks on Undirected Graphs Video
  7. Lesson 7 - Intro to Streaming, Morris Algorithm Video
  8. Lesson 8 - Reservoir Sampling Video
  9. Lesson 9 - Approximate Median Video

Week 4

  1. Lesson 1 : Overview Video
  2. Lesson 2 : Balls, bins, hashing Video
  3. Lesson 3 : Chain hashing, SUHA, Power of Two choices Video
  4. Lesson 4 : Bloom filter Video
  5. Lesson 5 : Pairwise independence Video
  6. Lesson 6 : Estimating expectation of continuous function Video

Week 5

  1. Lesson 1 - Universal hash functions Video
  2. Lesson 2 - Perfect hashing Video
  3. Lesson 3 - Count-min filter for heavy hitters in data streams Video
  4. Problem solving video - Doubly Stochastic Transition Matrix Video
  5. Problem solving video - Random Walks on Linear Structures Video
  6. Problem solving video - Lollipop Graph Video
  7. Problem solving video - Cat And Mouse Video

Week 6

  1. Lesson 1 - Estimating frequency moments Video
  2. Lesson 2 - Property testing framework Video
  3. Lesson 3 - Testing Connectivity Video
  4. Lesson 4 - Enforce & Test Introduction Video
  5. Lesson 5 - Testing if a graph is a biclique Video
  6. Lesson 6 - Testing bipartiteness Video

Week 7

  1. Lesson 1 - Property testing and random walk algorithms Video
  2. Lesson 2 - Testing if a graph is bipartite (using random walks) Video
  3. Lesson 3 - Graph streaming algorithms: Introduction Video
  4. Lesson 4 - Graph streaming algorithms: Matching Video
  5. Lesson 5 - Graph streaming algorithms: Graph sparsification Video

Week 8

  1. Lesson 1 - MapReduce Video
  2. Lesson 2 - K-Machine Model (aka Pregel Model) Video

Syllabus and materials

At NPTEL, as the course publishes them.

Credits and licence

Institution
IIT Madras
Department
Computer Science and Engineering
Teacher
Prof. John Augustine
Level
Undergraduate
Language
English
Subjects
Computer science, Engineering
Source
NPTEL
Licence
CC BY-NC-SA, as NPTEL states it. Non-commercial use only. NPTEL's terms
Attribution
NPTEL states: "Distributed under Creative Commons Attribution-ShareAlike / CC BY - NC - SA", beside a BY-NC-SA badge.
Who can watch
NPTEL gives no rating. Invisible Network shows it to Tweens profiles and older, judged from what the source says about it. How courses are placed