0
(
ratings
)
1
students
Created by:
Last updated:
Duration:
This course includes:
Unlimited Duration
Badge on Completion
Certificate of completion
Unlimited Duration
Description
Algorithms for Big Data. Instructor: Prof. John Augustine, Department of Computer Science and Engineering, IIT Madras. In this course, you will learn how to design and analyse algorithms in the streaming and property testing models of computation. The algorithms will be analysed mathematically, so it is intended for a mathematically mature audience with prior knowledge of algorithm design and basic probability theory.
Traditional algorithms work well when the input data fits entirely within memory. In many modern application contexts, however, the size of the input data is too large to fit within memory. In some cases, data is stored in large data centres or clouds and specific parts of it can be accessed via queries. In some other application contexts, very large volume of data may stream through a computer one item at a time. So the algorithm will get to see the data typically as a single pass, but will not be able to store the data for future reference. In this course, we will introduce computational models, algorithms and analysis techniques aimed at addressing such big data contexts. (from nptel.ac.in)
Course Curriculum
- Lecture 01 – Basic Definitions: Basics of Probability Theory Unlimited
- Lecture 02 – Conditional Probability Unlimited
- Lecture 03 – Examples – How to Use Probability to Solve Problems Unlimited
- Lecture 04 – Karger’s Mincut Algorithm Unlimited
- Lecture 05 – Analysis of Karger’s Mincut Algorithm Unlimited
- Lecture 07 – Randomized Quicksort Unlimited
- Lecture 08 – Problem Solving Example – The Rich Get Richer Unlimited
- Lecture 09 – Problem Solving Example – Monty Hall Problem Unlimited
- Lecture 10 – Bernoulli, Binomial, and Geometric Distributions Unlimited
- Lecture 11 – Tail Bounds Unlimited
- Lecture 12 – Application of the Chernoff Bound Unlimited
- Lecture 13 – Application of Chebyshev’s inequality Unlimited
- Lecture 14 – Introduction to Big Data Algorithms Unlimited
- Lecture 15 – SAT Problem Unlimited
- Lecture 16 – Classification of States Unlimited
- Lecture 17 – Stationary Distribution of a Markov Chain Unlimited
- Lecture 18 – Celebrities Case Study Unlimited
- Lecture 21 – Reservoir Sampling Unlimited
- Lecture 22 – Approximate Median Unlimited
- Lecture 23 – Hashing and Pairwise Independence: Overview Unlimited
- Lecture 24 – Balls, Bins, Hashing Unlimited
- Lecture 25 – Chain Hashing, SUHA, Power of Two Choices Unlimited
- Lecture 26 – Bloom Filter Unlimited
- Lecture 27 – Pairwise Independence Unlimited
- Lecture 28 – Estimating Expectation of Continuous Function Unlimited
- Lecture 29 – Universal Hash Functions Unlimited
- Lecture 30 – Perfect Hashing Unlimited
- Lecture 31 – Count-Min Filter for Heavy Hitters in Data Streams Unlimited
- Lecture 32 – Problem Solving – Doubly Stochastic Transition Matrix Unlimited
- Lecture 33 – Problem Solving – Random Walks on Linear Structures Unlimited
- Lecture 33 – Problem Solving – Random Walks on Linear Structures Unlimited
- Lecture 34 – Problem Solving – Lollipop Graph Unlimited
- Lecture 35 – Problem Solving – Cat and Mouse Unlimited
- Lecture 36 – Estimating Frequency Moments Unlimited
- Lecture 37 – Property Testing Framework Unlimited
- Lecture 38 – Testing Connectivity Unlimited
- Lecture 40 – Testing if a Graph is a Biclique Unlimited
- Lecture 42 – Property Testing and Random Walk Algorithms Unlimited
- Lecture 43 – Testing if a Graph is Bipartite (using Random Walks) Unlimited
- Lecture 44 – Graph Streaming Algorithms: Introduction Unlimited
- Lecture 45 – Graph Streaming Algorithms: Matching Unlimited
- Lecture 46 – Graph Streaming Algorithms: Graph Sparsification Unlimited
- Lecture 47 – MapReduce Unlimited
- Lecture 48 – K-Machine Model (aka Pregel Model) Unlimited
About the instructor
Instructor Rating
Reviews
Courses
Students
