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
Homework 2. Due date: 14/11/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]
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, Reservoir 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 (cont.), Morris Counter, Median of Means
[MMD, Chapter 4.3], [AMD, Chapters 3.1, 5.5, 2.2.4], [DSA, Chapter 4]
Tue, 21/10: Streaming: Frequency Estimation (Majority, Misra-Gries, Count-Min Sketch)
[AMD, Chapters 5.3], [DSA, Chapters 1, 5.4, 5.5]
Thu, 23/10: Streaming: Count-Min Sketch (cont.); Cardinality Estimation: Flajolet-Martin's LogLog Algorithm
[MMD, Chapter 4.4], [AMD, Chapters 5.4], [DSA, Chapter 2]
Tue, 28/10: Streaming: Count 1's: DGIM and Sum Integers; Homework 1 Solutions
Thu, 30/10: Market-Basket Model: Association Rules, Frequent Itemsets Algorithms (Apriori, SON)
[MMD, Chapters 6.1, 6.2, 6.4]
Tue, 04/11: Market-Basket Model: Frequent Itemsets Algorithms (SON, Random Sampling, Toivonen)
[MMD, Chapter 6.4]
ARMED Testing [AST 22]
Thu, 06/11: Similarity Search: Hash Functions (Uniform, k-wise Independent, Universal), Metric Spaces (Distances: Minkowski, Jaccard, Hamming, Cosine, Edit)
[AMD, Chapter 2.3], [MMD, Chapter 3.5]
[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]