# Algorithms for Big Data

- Institution: IIT Madras
- Department: Computer Science and Engineering
- Teacher: Prof. John Augustine
- Level: Undergraduate
- Language: English
- Subjects: Computer science, Engineering
- Source: [NPTEL](https://nptel.ac.in/courses/106106142)
- Licence: [CC BY-NC-SA](https://nptel.ac.in/faq) (Non-commercial use only.)
- Syllabus: [at the source](https://nptel.ac.in/courses/106106142)
- Who can watch: Tweens profiles and older (sources give no ratings; placed by Invisible Network from the source's own words)

## Lectures

1. [Lesson 1 - Basic definitions](https://invisiblenetwork.ai/learn/nptel/106106142/3418e1817780) (Video)
2. [Lesson 2 - Conditional probability](https://invisiblenetwork.ai/learn/nptel/106106142/e920f3da06f7) (Video)
3. [Lesson 3 - Example problems](https://invisiblenetwork.ai/learn/nptel/106106142/1ab94bd48d5e) (Video)
4. [Lesson 4 - Karger's mincut algorithm](https://invisiblenetwork.ai/learn/nptel/106106142/163e4b2bafad) (Video)
5. [Lesson 5 - Analysis of Karger's mincut algorithm](https://invisiblenetwork.ai/learn/nptel/106106142/f061913bf4ac) (Video)
6. [Lesson 6 - Random variables](https://invisiblenetwork.ai/learn/nptel/106106142/229c6b5eb597) (Video)
7. [Lesson 7 - Randomized quicksort](https://invisiblenetwork.ai/learn/nptel/106106142/a3d37b409dc6) (Video)
8. [Problem solving video - The rich get richer](https://invisiblenetwork.ai/learn/nptel/106106142/c92bccb2c9ee) (Video)
9. [Problem solving video - Monty Hall problem](https://invisiblenetwork.ai/learn/nptel/106106142/7c40db169418) (Video)
10. [Lesson 1 - Bernoulli, Binomial, and Geometric distributions](https://invisiblenetwork.ai/learn/nptel/106106142/f047735c2b0d) (Video)
11. [Lesson 2 - Tail Bounds](https://invisiblenetwork.ai/learn/nptel/106106142/bfdbe0a5c34f) (Video)
12. [Lesson 3 - Application of Chernoff bound](https://invisiblenetwork.ai/learn/nptel/106106142/f0ddfb7e8d9b) (Video)
13. [Lesson 4 - Application of Chebyshev's inequality](https://invisiblenetwork.ai/learn/nptel/106106142/e0185183921e) (Video)
14. [Lesson 1 - Intro to Big Data Algorithms](https://invisiblenetwork.ai/learn/nptel/106106142/b51c1368583b) (Video)
15. [Lesson 2 - SAT Problem](https://invisiblenetwork.ai/learn/nptel/106106142/a78a6a486a90) (Video)
16. [Lesson 3 - Classification of States](https://invisiblenetwork.ai/learn/nptel/106106142/f7756bf887e3) (Video)
17. [Lesson 4 - Stationary Distribution of a Markov Chain](https://invisiblenetwork.ai/learn/nptel/106106142/75e6eb8f8d03) (Video)
18. [Lesson 5 - Celebrities Case Study](https://invisiblenetwork.ai/learn/nptel/106106142/01c4787ad430) (Video)
19. [Lesson 6 - Random Walks on Undirected Graphs](https://invisiblenetwork.ai/learn/nptel/106106142/96a68784d70b) (Video)
20. [Lesson 7 - Intro to Streaming, Morris Algorithm](https://invisiblenetwork.ai/learn/nptel/106106142/212b67cc075f) (Video)
21. [Lesson 8 - Reservoir Sampling](https://invisiblenetwork.ai/learn/nptel/106106142/c5117e1ba7f5) (Video)
22. [Lesson 9 - Approximate Median](https://invisiblenetwork.ai/learn/nptel/106106142/f78ac9c672bc) (Video)
23. [Lesson 1 : Overview](https://invisiblenetwork.ai/learn/nptel/106106142/d9e279cc22f2) (Video)
24. [Lesson 2 : Balls, bins, hashing](https://invisiblenetwork.ai/learn/nptel/106106142/d885ecba7269) (Video)
25. [Lesson 3 : Chain hashing, SUHA, Power of Two choices](https://invisiblenetwork.ai/learn/nptel/106106142/23898f87ac5f) (Video)
26. [Lesson 4 : Bloom filter](https://invisiblenetwork.ai/learn/nptel/106106142/ae9a7d2932ef) (Video)
27. [Lesson 5 : Pairwise independence](https://invisiblenetwork.ai/learn/nptel/106106142/031f665002f5) (Video)
28. [Lesson 6 : Estimating expectation of continuous function](https://invisiblenetwork.ai/learn/nptel/106106142/ddeb833be55d) (Video)
29. [Lesson 1 - Universal hash functions](https://invisiblenetwork.ai/learn/nptel/106106142/b7d2550f6572) (Video)
30. [Lesson 2 - Perfect hashing](https://invisiblenetwork.ai/learn/nptel/106106142/e9f191214398) (Video)
31. [Lesson 3 - Count-min filter for heavy hitters in data streams](https://invisiblenetwork.ai/learn/nptel/106106142/5015a54ba4cd) (Video)
32. [Problem solving video - Doubly Stochastic Transition Matrix](https://invisiblenetwork.ai/learn/nptel/106106142/2d17494c042b) (Video)
33. [Problem solving video - Random Walks on Linear Structures](https://invisiblenetwork.ai/learn/nptel/106106142/009781599d65) (Video)
34. [Problem solving video - Lollipop Graph](https://invisiblenetwork.ai/learn/nptel/106106142/6a6d6ff60fb7) (Video)
35. [Problem solving video - Cat And Mouse](https://invisiblenetwork.ai/learn/nptel/106106142/f1a3c504a076) (Video)
36. [Lesson 1 - Estimating frequency moments](https://invisiblenetwork.ai/learn/nptel/106106142/44ce104d7ce7) (Video)
37. [Lesson 2 - Property testing framework](https://invisiblenetwork.ai/learn/nptel/106106142/0bcd3658bb38) (Video)
38. [Lesson 3 - Testing Connectivity](https://invisiblenetwork.ai/learn/nptel/106106142/d6d828cecda7) (Video)
39. [Lesson 4 - Enforce & Test Introduction](https://invisiblenetwork.ai/learn/nptel/106106142/b93649aa3a56) (Video)
40. [Lesson 5 - Testing if a graph is a biclique](https://invisiblenetwork.ai/learn/nptel/106106142/7b7197dc74c5) (Video)
41. [Lesson 6 - Testing bipartiteness](https://invisiblenetwork.ai/learn/nptel/106106142/1ed35b08856a) (Video)
42. [Lesson 1 - Property testing and random walk algorithms](https://invisiblenetwork.ai/learn/nptel/106106142/d7e35fc477e7) (Video)
43. [Lesson 2 - Testing if a graph is bipartite (using random walks)](https://invisiblenetwork.ai/learn/nptel/106106142/44890466959a) (Video)
44. [Lesson 3 - Graph streaming algorithms: Introduction](https://invisiblenetwork.ai/learn/nptel/106106142/e4d77b84c93d) (Video)
45. [Lesson 4 - Graph streaming algorithms: Matching](https://invisiblenetwork.ai/learn/nptel/106106142/562517628c17) (Video)
46. [Lesson 5 - Graph streaming algorithms: Graph sparsification](https://invisiblenetwork.ai/learn/nptel/106106142/ca23888930e3) (Video)
47. [Lesson 1 - MapReduce](https://invisiblenetwork.ai/learn/nptel/106106142/e1630e9d8f2d) (Video)
48. [Lesson 2 - K-Machine Model (aka Pregel Model)](https://invisiblenetwork.ai/learn/nptel/106106142/a9fa1d2901eb) (Video)