Learn · Algorithms for Big Data

Lecture 44 of 48Week 7

Lesson 3 - Graph streaming algorithms: Introduction

Prof. John Augustine · IIT Madras

Credits and licence

From
Algorithms for Big Data, IIT Madras (at NPTEL)
Licence
CC BY-NC-SA, as NPTEL states it. Non-commercial use only.
Attribution
NPTEL states: "Distributed under Creative Commons Attribution-ShareAlike / CC BY - NC - SA", beside a BY-NC-SA badge.
Who can watch
Tweens profiles and older. How courses are placed

All the lectures

  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
  10. Lesson 1 - Bernoulli, Binomial, and Geometric distributions Video
  11. Lesson 2 - Tail Bounds Video
  12. Lesson 3 - Application of Chernoff bound Video
  13. Lesson 4 - Application of Chebyshev's inequality Video
  14. Lesson 1 - Intro to Big Data Algorithms Video
  15. Lesson 2 - SAT Problem Video
  16. Lesson 3 - Classification of States Video
  17. Lesson 4 - Stationary Distribution of a Markov Chain Video
  18. Lesson 5 - Celebrities Case Study Video
  19. Lesson 6 - Random Walks on Undirected Graphs Video
  20. Lesson 7 - Intro to Streaming, Morris Algorithm Video
  21. Lesson 8 - Reservoir Sampling Video
  22. Lesson 9 - Approximate Median Video
  23. Lesson 1 : Overview Video
  24. Lesson 2 : Balls, bins, hashing Video
  25. Lesson 3 : Chain hashing, SUHA, Power of Two choices Video
  26. Lesson 4 : Bloom filter Video
  27. Lesson 5 : Pairwise independence Video
  28. Lesson 6 : Estimating expectation of continuous function Video
  29. Lesson 1 - Universal hash functions Video
  30. Lesson 2 - Perfect hashing Video
  31. Lesson 3 - Count-min filter for heavy hitters in data streams Video
  32. Problem solving video - Doubly Stochastic Transition Matrix Video
  33. Problem solving video - Random Walks on Linear Structures Video
  34. Problem solving video - Lollipop Graph Video
  35. Problem solving video - Cat And Mouse Video
  36. Lesson 1 - Estimating frequency moments Video
  37. Lesson 2 - Property testing framework Video
  38. Lesson 3 - Testing Connectivity Video
  39. Lesson 4 - Enforce & Test Introduction Video
  40. Lesson 5 - Testing if a graph is a biclique Video
  41. Lesson 6 - Testing bipartiteness Video
  42. Lesson 1 - Property testing and random walk algorithms Video
  43. Lesson 2 - Testing if a graph is bipartite (using random walks) Video
  44. Lesson 3 - Graph streaming algorithms: Introduction Video
  45. Lesson 4 - Graph streaming algorithms: Matching Video
  46. Lesson 5 - Graph streaming algorithms: Graph sparsification Video
  47. Lesson 1 - MapReduce Video
  48. Lesson 2 - K-Machine Model (aka Pregel Model) Video