AD4DA (a.a. 2025‐26) - ferragina/AD2DA GitHub Wiki
This is the material for the course "Algorithms and Data structures for Data-intensive Applications", taught in the master's program in Informatics for Digital Health, held at the Department of Computer Science of the University of Pisa.
Teachers: Paolo Ferragina and Giovanni Manzini
CFU: 9 (first semester).
Course ID: 0002A.
Language: English.
Question time: Paolo Ferragina: by appointment (also in video-conferencing through the virtual room of the course). Giovanni Manzini: Tuesday 10:00 AM room 294, or by appointment.
News: about this course will be distributed via a Telegram channel.
Official lectures schedule: The schedule and content of the lectures are available below and with the official registro.
The course consists of 2 hours of lectures in the first three days of the week, from 11 AM to 1 PM.
- Monday: 11:00 - 13:00, Room PS4
- Tuesday: 11:00 - 13:00, Room PS4
- Wednesday: 11:00 - 13:00, Room Fib M1
The exam will consist of a written test including two parts: exercises and "oral" questions. The exam is passed if in both parts the student gets a sufficient score (expressed in 30), which is then averaged.
The first (exercises) and the second (theory questions) parts of the exam can be split into different exam dates, even of different exam sessions. The exam dates are indicated in the calendar on ESAMI. In the case that the second part is not passed or the student abandons the exam, (s)he can keep the rank of the first exam, but this may occur just once. The second time this happens, the rank of the first part is dropped, and the student has to do both parts again.
The goal of this course is to enrich and strengthen the knowledge about basic algorithms and data structures, learned in undergraduate courses, with further models, methodologies, tools, and techniques to design, analyze, experiment, and improve solutions for managing massive datasets of multimodal types: integer, string, vector, text, time series, and (labeled) graph.
This knowledge and skills constitute the building blocks upon which Big Data platforms and applications are built (e.g., key-value stores, graph DBs, vector DBs, Transformers, …), so this theoretical part will provide students with the “methodological toolbox” for designing and evaluating their big data solutions, and for choosing the right library to adopt for their implementation.
The theoretical lectures will be complemented by some hands-on experience in coding with relevant programming libraries that offer the above-mentioned building blocks. The course provides most of the algorithmic prerequisites for the other courses of this master’s degree.
- Key issues about I/Os, streaming, and hierarchical memory in managing massive datasets.
- Algorithmic and data structure issues concerning atomic versus variable-length items.
- Three fundamental tools: sorting, permuting, and sampling.
- Key-value stores: From basic to advanced hash tables and tries.
- Textual search engines: compressing and accessing posting lists (integer sequences) and text collections. Deduplicating similar/equal texts, clustering text collections.
- Bio-Informatics engines: compressing and indexing arbitrary text for exact substring search.
- Vector DBs: nearest neighbor search, hamming, or Euclidean distance.
- Advanced storage: Streaming and random access to compressed raw files, time series, and (labeled) graphs.
Lectures will include in-depth discussions on the practical efficiency of the proposed algorithms and data structures, plus hands-on experience with coding solutions for some topics.
I strongly suggest refreshing your knowledge about basic Algorithms and Data Structures by looking at the well-known book Introduction to Algorithms, Cormen-Leiserson-Rivest-Stein (third edition). Specifically, I suggest you look at the chapters 2, 3, 4, 6, 7, 8, 10, 11 (no perfect hash), 12 (no randomly built), 15 (no optimal BST), 18, 22 (no strongly connected components). Also, you could look at the Video Lectures, by Erik Demaine and Charles Leiserson, specifically Lectures 1-7, 9-10, and 15-17.
The content of the course will be covered mostly by the book published by Cambridge University Press as Pearls of Algorithm Engineering (with its Errata Corrige), and in some small parts by notes and GitHub refs that will provide the materials of hands-on sessions.
If students wish to train themselves on the topics of this course, they can select some useful exercises from the following superset.
| Date | Topic | Notes and Refs |
|---|---|---|
| 15/09/25 | Key issues about I/Os, RAM *versus* two-level memory model, (asymptotic) time and I/O-complexity, the role of the hierarchical memory in managing massive datasets, an example of I/O-analysis. | Chap. 1 |
| 16/09/25 | Some example of I/O-analysis: binary search versus B-tree search. Sorting versus Permuting, RAM versus two-level memory model. Designing a scan_and_sort-based permuter. I/O-complexity of sorting and permuting. I/O-complexity of the binary mergesort. | Sect. 5.1, 5.1.1. Read B-tree note 1 and note2 |
| 17/09/25 | Multi-way mergesort: I/O complexity and examples or real cases. The case of D disks, and the disk striping technique. Key-value stores: an introduction. Randomised data structure: skip list, with its time and space complexity. | Sect. 5.1 (no 5.1.2), 5.1.3 and 5.4 (no GreedSort), and notes on skip-list (i.e. Sect 8.5) |
| 22/09/25 | No lecture because rooms were not accessible. | |
| 23/09/25 | The structure of a (Web) search engine: crawler, indexer, retriever, ranker. Inverted list: dictionary + posting lists, with examples. List intersection: merge-based approach, binary-search-based approach, mutual partitioning, and two-level intersection. | Chap. 6 |
| 24/09/25 | Uncompacted trie and compacted trie, implementation with hash tables, and analysis of time and space. How to index a dictionary of variable-length strings: (un)compacted tries, and two-level indexing with Front coding. Exercise on two-level indexing. | Sect. 9.1, 9.1.1, 9.1.2, 9.4, 9.5. |
| 29/09/25 | Patricia Trie and its use in the two-level indexing scheme. Textual ranking: TF-IDF, the vector space model, the case of sparse vectors, cosine similarity and its computation via Inverted Lists. | Sect. 9.5. Slides |
| 30/09/25 | Some approaches to speed up the computation of the "best" documents for a query: using IDF, using the term weights, or via clustering. Auto-completion search in a dictionary of strings. Exercises on two-level indexing (with Patricia Trie and Front coding), and on TF-IDF. | |
| 01/10/25 | The problem of searching strings with e-errors in a dictionary. The case of (weighted) edit distance and the use of Dynamic Programming, with its time and space complexity. On the overlap distance and k-grams, and how to use them to approximate the edit distance. An example of overlap distance calculation on a dictionary of strings. | |
| 06/10/25 | An example of a hybrid search engine and retrieval augmented generation, via Weaviate. On creating a text-based search engine using the well-known vector database Weaviate. Specifically, we focused on indexing and querying a textual collection and performing pure textual queries with bm25, vectorized queries with text-embedding models, and hybrid queries. A sketch of a RAG via Weaviate. | Notebook and talk by Lorenzo Bellomo |
| 07/10/25 | Sorting atomic items. Lower bound for the comparison model. Quicksort: strategies for pivot selection, binary and ternary partition. | Sects. 5.2, 5.3 |
| 08/10/25 | Analysis of Quicksort with random pivot selection. Bounding the stack space usage. Sorting strings: definition of the problem and lower bounds. | Sect. 5.3, Chap. 7 |
| 13/10/25 | Sorting strings: LSD and MSD radix sort. Multi-key Quicksort and ternary search trees. Proof of correctness. Analysis and comparison of their time complexities. | Chap. 7 |
| 14/10/25 | Locality sensitive hashing, off-line and on-line over hamming distance, the case of Cosine-based similarity, with their probabilistic analysis. An exercise. | Slides |
| 15/10/25 | Exact and near duplicate matches in documents. Locality sensitive hashing: the case of documents; shingling, Jaccard similarity and its sketches, with their probabilistic analysis. | |
| 20/10/25 | The Dictionary problem: Direct-Address Tables, Hash tables with chaining, results for simple uniform hashing. Universal Hashing (1). | Sects 8.1, 8.2, 8.3 |
| 21/10/25 | Universal Hashing (2). Universal hash functions. Power of 2 choices. Cuckoo Hashing (1). | Sects 8.3 (no proof of Theorem 8.3), 8.5 |
| 22/10/25 | Cuckoo Hashing (2), Order Preserving Minimal Perfect Hashing (1) | Sects 8.5, 8.6 |
| 27/10/25 | Order Preserving Minimal Perfect Hashing (2), Bloom filters (1). | Sects 8.6, 8.7 |
| 28/10/25 | Bloom filters: Analysis, lower bound, and variants. | Sect 8.7 |
| 29/10/25 | Exercises for the midterm exam | Text and solution |
| 3/11/25 | Set intersection using Bloom filters. Exercises on hash tables and Bloom filters. | Sect 8.7.2 |
| 4/11/25 | Midterm Exam | |
| 5/11/25 | Integer coding. Prefix free codes: Unary, Elias Gamma and Elias Delta | Sects 11, 11.1 |
| 10/11/25 | Kraft inequality and the optimal length of an instantaneous code. Variable-byte code (1). | Sect 11.4. Slides |
| 11/11/25 | Variable-byte code (2). (s,c) dense codes. Elias-Fano code: description and space bound. | Sects 11.4, 11.6. Slides Python notebook |
| 12/11/25 | Elias-Fano code: Access and NextGEQ operations. Rank/Select operations on binary strings. Wavelet trees and rank/select operations on arbitrary strings. | Sects 11.6, 15.1 Slides Elias Fano, Slides rank/select, Python notebook |
| 17/11/25 | Substring search: suffix tries and suffix trees. | Sect. 10.1, 10.2, 10.3. Slides: suffix tries, suffix trees |
| 18/11/25 | Exercise: finding repetitions on suffix trees. Suffix arrays and LCP arrays. | Sect. 10.1, 10.2, 10.3. Slides: suffix arrays |
| 24/11/25 | Suffix Array construction in linear time using the Skew (DC3) algorithm. Building the suffix tree from the suffix/LCP arrays. Python code for suffix tree construction and search. Exercise: finding repetitions using suffix arrays and LCP arrays. | Sect. 10.2, 10.3. Slides: suffix array construction Code: Suffix Tree class in Python |
| 25/11/25 | The Burrows-Wheeler transform. Computation from the SA and inversion | Sect. 14.1. Slides: bwt properties, Code: bwt computation and inversion |
| 26/11/25 | Example of BWT inversion. The BWT as a compressed SA: the FM-index. | Sect. 14.5. Slides: /FM-indices |
| 1/12/25 | Comparison of different FM-index implementations (Wavelet Tree vs checkpoints). Exercise on counting the occurrences using a BWT. Compression of integer arrays | Slides: FM-index Sect. 15.1 |
| 2/12/25 | Succinct representations of trees | Sect. 15.2. Slides: succinct trees |
| 3/12/25 | Succinct representations of graphs | Sect. 15.3 |
| 10/12/25 | Exercises for the final exam | |
| 17/12/25 | Final exam, room M1, 11:00 AM | text, solution. |