Algoritmi Per I Big Data 2025/2026

PART A: Probability and Computing: Randomized Algorithms for Big Data

Basic Notions of Probability (Chapt 1 of [2])

Verifying Polynomial Identities (Chapt 1.1 of [2],

Verifying Matrix Multiplications (Chapt. 1.3 of [2],

Contention Resolutions (Chapt 13 of [3])

Randomized Quick-Sort (Chapt. 2.5 of [2])

Randomized Algorithms for Computing the Median ( Chapt 3.4 of [2])

Randomized Hash Functions, and Hash Tables*, (Chapt 13.6 of [3] vedi anche Ssection 2.3 in [4]*)



PART B: Data Mining

Data Mining: A Short Overview (Chapt 1 of [1])

Finding Similar Items (Chapt 3 of [1] + )

Applications of Set Similarity

Shingling of Documents

Similarity-preserving Summaries of Sets

Locality Sensing Hashing for Documents

Mining Data Streams (Chapt 4 of [1])

The Stream Data Model

Pattern Matching: Karp-Rabin’s Algorithm (Ssection 3.1 and 4.1 in [4])

Sampling Data in a Stream

Filtering Stream

Counting Distinct Elements in a Stream

Estimating Moments of a Stream

Random Walks & Page Rank

Random Walks (Section 4 of [5])

Page Rank Algorithms for the WEB (Sec 5 of [1]]



Books:

[1] Leskovec, Rajaraman, and Ullamann: Mining of Massive Data Sets

[2] Mitzenmacher and Upfal: Probability and Computing (Cambridge)

[3] Kleinberg and Tardos: Algorithm Design

[4] Nicola Prezza: Algorithms for Massive Data (Notes)

[5] Foundations of Data Science, Avrim Blum, John Hopcroft, Ravindran Kannan

---

Fonte: GOMP