CSL7030: Algorithms for Big Data (winter 2020)

• Credits L-T-P [C]: 2-0-0 [2]
• Where: Google Meet https://meet.google.com/rni-yevq-yhi

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

Learning Materials

1. Scribing of Lectures Algorithms for Big Data By Prof. Jelani Nelson, Harvard University

2. Algorithmic Techniques for Big Data Analysis By Prof. Barna Saha, University of Minnesota Twin Cities

3. https://www.sketchingbigdata.org/

Grading Policy

• Quiz: 20% (https://www.classmarker.com/)
• Review Project: 20%
• Presentation + Viva: 20% (dates to be announced)
• Major: 40%

Quiz

• There will be 3 to 4 Quizzes
• Dates and Syllabus will be announced in Classroom

Review Project

• 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.)

Presentation + Viva

• Between Jan 18-30, 2021
• Exact dates will be announced latter