AD4DA (a.a. 2026‐27) - 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: by appointment on Teams' channel, or at the end of the lectures.

News: about this course will be distributed via a Telegram channel.

Official lecture schedule: The schedule and lecture content are available below and in the official registro.

The course consists of 2 hours of lectures on 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 Fib I-lab
• Wednesday: 11:00 - 13:00, Room Fib I-lab

The exam will consist of a written test including two parts: exercises and "theory" questions. The exam is passed if in both parts the student gets a sufficient score (out of 30), which is then averaged.

The first (exercises) and the second (theory questions) parts of the exam can be split into different exam dates. The exam dates are indicated in the calendar on ESAMI. If a student decides to repeat an exam's part to improve it, as soon as (s)he participates in the exam (s)he loses the previous grade.

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 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	Refreshed some basic concepts in algorithm analysis: the RAM model, time and space complexity, asymptotic analysis, and polynomial versus exponential algorithms. Key issues about I/Os and hierarchical memory in managing massive datasets. The two-level memory model and I/O-costs. An example of I/O-analysis on the simple problem of summing items stored in an array.	Chap 1
16/09/26	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
	Students are warmly invited to refresh their know-how about the divide-and-conquer technique for algorithm design and Master Theorem for solving recurrence relations; and Binary Search Trees.	Lectures of Demaine's course
21/09/26	Multi-way mergesort: I/O complexity and examples or real cases. The case of D disks, and the disk striping technique. The Snow Plow technique, with examples.	Sect. 5.1, 5.1.2, 5.1.3 and 5.4 (no GreedSort)
22/09/26	NO LECTURE
23/09/26	Random sampling: definition, Reservoir sampling algorithm. Key-value stores: an introduction. Randomised data structure: skip list, with its time and space complexity.	sect. 3.3 and notes on skip-list (i.e. Sect 8.5)
28/09/26	Sorting strings: Multi-key Quicksort. Proof of correctness and time complexity. Lower bound on sorting strings. Ternary search trees: definition, construction, search by exact match, prefix, lexicographic, and range. Exercises.	Sect. 7.1 and 7.3.
29/09/26	Uncompacted trie and compacted trie, implementation with triples for edge labels, 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. How to implement search by exact match, prefix, lexicographic, and range. Auto-completion search: definition and implementation via tries. Exercises.	Sect. 9.1, 9.1.1, 9.1.2, 9.4, 9.5.
30/09/26	Patricia Trie and its use in the two-level indexing scheme. Exercise.	Sect. 9.5.
5/10/26	Codes: nonsingular, uniquely decodable and prefix free (istantaneous). Kraft inequality. Integer coding. Prefix free integer codes: Unary and Elias Gamma. Optimal length of an instantaneous code.	Sects 11, 11.1. Slides
6/10/26	Entropy and its relationship with Huffman codes. Elias delta code. Variable-byte codes.	Sect 12.1, 11.1, 11.4 Slides Python notebook
7/10/26	Elias-Fano code: description, space bound and access operation. Exercises on the different integer coding schemes.	Sects 11.6Slides Elias Fano
12/10/26	Rank/Select operations on binary strings. Elias-Fano code: nextGEQ operation. Exercises on Elias-Fano coding.	Sects 11.6, 15.1.1 Slides rank/select (up to page 6).
13/10/26 (morning)	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
13/10/26 (afternoon)	Intersection by multiple terms. Textual ranking: TF-IDF, the vector space model, the case of sparse vectors, document similarity based on cosine or Euclidean distance or scalar product. Some approaches to speed up the computation of the "best" documents for a query: using the top-k best TF-IDF of a term, or via clustering.
14/10/26	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.	Slides
*******	OLD TOPICS TO BE UPDATED	*******
//26	Locality sensitive hashing, off-line and on-line over hamming distance, the case of Cosine-based similarity, with their probabilistic analysis. An exercise.	Slides
//26	Exact and near duplicate matches in documents. Locality sensitive hashing: the case of documents; shingling, Jaccard similarity and its sketches, with their probabilistic analysis.