CSL7030: Algorithms for Big Data (winter 2020)

Syllabus

Introduction: Randomized algorithms, Universal Hash Family, Probabilistic Algorithm Analysis, Approximation Algorithms, $\epsilon$-Approximation Schemes.
Sketching and Streaming: Extremely Small-Space Data Structures, CountMin Sketch, Count Sketch, Turnstile Streaming, AMS Sketch, Graph Sketching, Graph Connectivity
Map-Reduce: Map-Reduce Algorithms in Constrains Settings such as small memory, few machines, few rounds, and small total work, Efficient Parallel Algorithms
External memory and cache-obliviousness: Minimizing I/O for large datasets, Algorithms and data structures such as B-trees, Buffer trees, Multiway merge sort

Scribing of Lectures Algorithms for Big Data By Prof. Jelani Nelson, Harvard University
Algorithmic Techniques for Big Data Analysis By Prof. Barna Saha, University of Minnesota Twin Cities
https://www.sketchingbigdata.org/

Goal is to write a review on a specific topic of “Algorithms for Big Data”
The review should be comprehensive between 3000-4000 words. Do not write review only on one/two papers.
Review should be submitted with Single Column, double spacing pdf generated with LaTeX (use any standard template e.g., ACM, IEEE, Elsevier etc.)

You may work in a group of 2/3 person. Expectation of larger group will be higher.

Plagiarism tolerance is 7% from single source and 15% cumulative, anything more leads to lower or no marks at all.

Last updated on Nov 30, 2020