Instructor: Emilio Cruciani
Course Title: IN1040 - Tópicos Avançados em Algoritmos e Complexidade 2: Big Data Algorithms
When: Tuesdays 13:00-15:00 & Thursdays 15:00-17:00 (30/09/2025 - 16/12/2025)
Room: A014
Office Hours: Before/after class or contact the instructor via email (emilio.cruciani@unier.it)
Modern data is vast, fast, and often high-dimensional. From billions of daily web searches to social media streams and sensor networks, making sense of large-scale data requires algorithmic tools that go beyond traditional approaches. This course offers an introduction to scalable algorithms for massive datasets, covering topics such as streaming, sketching, locality-sensitive hashing, graph analysis, dimensionality reduction, clustering.
The evaluation will be based on a set of four homeworks. Collaboration for the homeworks is allowed, but write-up should be done individually. Every homework must be hand in by email to the instructor by the due date. Homeworks that are late will lose 10% of the grade if they are up to 1 day (24h) late, 20% if they are 2 days late, 30% if they are 3 days late, and they will receive no credit if they are late for more than 3 days. However, you have a bonus of 3 late days, which you can distribute as you wish among all the homeworks. In addition, we will take into account participation during class.
Homework 1. Due date: 24/10/2025, 23:59
Thu, 11/09: Course Introduction: Big Data, Topics, Tools
[slides]
Tue, 30/09: Probability: Probability Spaces, Union Bound, Monty Hall problem, Independent Events, Verification of Polynomials
[PAC, Chapter 1]
Model of computation, Randomized Algorithms, Boost Probability by Repeating a Bunch of Times [video]
Thu, 02/10: Probability: Conditional Probability, Law of Total Probability, Bayes' Law, Karger's Min-Cut Algorithm, Karger-Stein's Algorithm
[PAC, Chapter 1], [lecture notes, lecture notes]
Optional: Karger-Stein's Algorithm [original paper], Max-Flow in Almost-Linear Time [arxiv]
Tue, 07/10: Probability: Random Variables, Expectation (Linearity of Expectation, Conditional Expectation); Bernoulli, Binomial, Geometric Random Variables; Coupon Collector's problem
[PAC, Chapter 2]
Thu, 09/10: Probability: Markov Inequality; Variance, Covariance, Chebyshev Inequality; Chernoff Bounds (for Binomial Random Variables)
[PAC, Chapters 3, 4]
Tue, 14/10: Streaming: Model, Sampling, Bloom Filters
[MMD, Chapter 4.1, 4.2, 4.3], [AMD, Chapter 3.1], [Reservoir sampling: lecture notes]
Thu, 16/10: Streaming: Bloom Filters, Morris Counter, Median of Means
[AMD, Chapters 3.1, 5.5, 2.2.4], [DSA, Chapter 4]
[AMD] Algorithms for Massive Data by Nicola Prezza [pdf]
[DSA] Data Stream Algorithms by Amit Chakrabarti [pdf]
[MMD] Mining of Massive Datasets by J. Leskovec, A. Rajaraman, and J. Ullman [website, pdf]
[PAC] Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis by M. Mitzenmacher, and E. Upfal [pdf v1, pdf v2]