Algorithm Engineering (a.a. 2024‐25) - ferragina/AlgorithmEngineering GitHub Wiki
This is the material for the course "Algorithms Engineering" taught (since 2009, see the historical Algorithm Engineering's original page) in the master programme in Computer Science and Networking, held at the Department of Computer Science of the University of Pisa
Teacher: Paolo Ferragina
CFU: 9 (first semester).
Course ID: 531AA.
Language: English.
Question time: Monday: 15-17, or by appointment (also in video-conferencing through the virtual room of the course)
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.
In this course, we will study, design, and analyze advanced algorithms and data structures for the efficient solution of combinatorial problems involving all basic data types, such as integers, strings, (geometric) points, trees, and graphs. The design and analysis will involve several models of computation— such as RAM, 2-level memory, cache-oblivious, and streaming— in order to take into account the architectural features and the memory hierarchy of modern PCs and the availability of Big Data upon which those algorithms could work. We will add to such theoretical analysis several other engineering considerations spurring from the implementation of the proposed algorithms and from experiments published in the literature.
Every lecture will follow a problem-driven approach that starts from a real software-design problem, abstracts it in a combinatorial way (suitable for an algorithmic investigation), and then introduces algorithms aimed at minimizing the use of some computational resources like time, space, communication, I/O, energy, etc. Some of these solutions will be discussed also at an experimental level, in order to introduce proper engineering and tuning tools for algorithmic development.
The course consists of 2 hours of lectures in the first three days of the week, from 9 AM to 11 AM.
- Monday: 9:00 - 11:00, Room Fib C
- Tuesday: 9:00 - 11:00, Room Fib C1
- Wednesday: 9:00 - 11:00, Room Fib C
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 (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. If 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 schedule of the next exams follows, but the official dates/hours of the exams are in the website of the University of Pisa, where you have to register to participate in the exam.
- 11/11/2024, start at 09:00, rooms C and C1, MIDTERM: text, solution, results.
- 09/12/2024, start at 11:00, rooms C, FINAL TERM: text, solution, results.
- 10/01/2025, start at 11:00, rooms C: text, solution.
- 04/02/2025, start at 11:00, rooms C: text, solution.
- 03/06/2025: text.
- 23/06/2025: text, solution.
- 25/07/2025: text.
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).
If you wish to practice on the exercise part of the exam, here is a zipped file containing previous exercises.
The lectures below include also some EXTRA material, which is suggested to be read for students aiming for high rankings.
| Date | Topic | Notes and Refs |
|---|---|---|
| 16/09/24 | Refreshing some basic concepts on the analysis of algorithms: RAM model, time and space complexity, asymptotic analysis, 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 |
| 17/09/24 | Some example of I/O-analysis: binary search versus B-tree search. The role of the Virtual Memory system, a probabilistic analysis. Sorting versus Permuting, RAM versus two-level memory model. Permuting algorithm via sorting and scanning, and its I/O-bound. Comments on the I/O complexity of sorting and permuting. | Sect. 5.1. Read B-tree note1 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 recurrent relations; and Binary Search Trees. | Lectures 2, 9, and 10 of Demaine's course | |
| 18/09/24 | Binary MergeSort: I/O-analysis. Snow Plow, with complexity proof and an example. The case of D disks, and the disk striping technique with I/O evaluation. | Sect. 5.1.1, 5.1.2, and 5.4 (no Greed Sort). |
| 23/09/24 | The multi-way mergesort, with I/O analysis. Lower bound for sorting: comparisons and I/Os.
EXTRA is the lower bound on permuting (sect. 5.2.2). |
Sect. 5.1.3, 5.2 and 5.2.1. |
| 25/09/24 | Quicksort: recap on best-case, worst-case, and average-case with analysis. 2-way, 3-way and double-pivot partition for better in-memory quicksort. Bounded Quicksort with space analysis. | Sect. 5.3, 5.3.1, 5.3.2, 5.3.3 |
| 30/09/24 | Selection of kth ranked item in O(n log n) time, O(n log k) time, and in linear average time (with proof). Multi-way Quicksort: definition, design, and I/O-complexity. Selection of k-1 "good pivot" via Oversampling. | Sect. 5.3.4 |
| 01/10/24 | Proof of the expected time complexity of Multi-way Quicksort. Random sampling: disk model, known length (algorithms and proofs). Random sampling on the streaming model: known length. | Sect. 5.3.4, 3.1 and 3.2 |
| 02/10/24 | Reservoir sampling: Algorithm and proofs. Randomized data structures: skip list with time/space analysis and comments on I/Os. | Notes, and see Demaine's lecture num. 12 on skip lists. |
| 07/10/24 | Randomized data structures: Treaps with their various types of operations: search a key, 3-sided range query, insert, delete, split, merge, and proof of their time complexity. | See notes previous lecture |
| 08/10/24 | String sorting: comments on the difficulty of the problem on disk, the lower bound. Multi-key Quicksort: algorithm and analysis. Ternary search tree. | Sect. 7.1 and 7.3 |
| 09/10/24 | String sorting: LSD-radix sort, MSD-radix sort, uncompacted tries and their implementation with arrays and hash tables. Asymptotic analysis in time and space, and proof of correctness. | Sect. 7.2 |
| 14/10/24 | Prefix search: definition of the problem, reduction to lexicographic search of two types of pattern. Solution based on arrays, Front-coding, two-level indexing based on compacted tries, two-level indexing based on Patricia Tries. Analysis of space, I/Os, and time of all described solutions. | sect. 9.1, 9.4, 9.5. |
| 15/10/24 | Interpolation search and doubling/exponential search, with time and space analysis. Intersection problem: merge-based solution, binarySearch-based solution, and their analysis. Lower bound on the intersection problem. | sect. 9.3, 6.1 and 6.2. |
| 16/10/24 | More on the intersection problem: mutual partitioning, doubling, two-level scan. | Sect. 6.3 and 6.4 |
| 17/10/24 | Exercises. | |
| 21/10/24 | Substring search: definition, properties, reduction to prefix search. The Suffix Array. Binary searching the Suffix Array: p log n. Suffix Array construction via qsort and its asymptotic analysis. Array LCP and its construction in linear time, with example. Suffix trees: properties, construction from Suffix Arrays and LCP array. Search and mining algorithms over suffix arrays and suffix trees. | All Chap. 10, but NO pages 156-158 for the use of LCP to get p + log n search (lemma 10.2). NO Skew and scan-based algorithms. NO sect 10.3.3. In sect 10.4 do only 10.4.4 (text mining). |
| 22/10/24 | Hashing and hash tables: the dictionary problem, direct addressing, hashing with chaining, global rebuilding technique, time and space complexity. Computational unfeasibility of simple uniform hashing. | Chap. 8 (i.e. 8.1 and 8.2) |
| 28/10/24 | Universal hashing (definition and properties). Three examples of Universal Hash functions, one with correctness proof. The "power of two choices" result. | Sect. 8.3, study all theorems with proof, except Theo 8.3 without proof (only the statement). |
| 29/10/24 | Cuckoo hashing (with all proofs). | Sect 8.5. |
| 30/10/24 | Minimal ordered perfect hashing: definition, properties, construction, space, and time complexity. Bloom Filter: properties, construction, query and insertion operations, error estimation (with proofs). | Sect. 8.6 and 8.7 (extra is 8.7.1, Lower bound on BF space; don't do compressed BF) |
| 31/10/24 | Exercises on midterm topics. | |
| 04/11/24 | Discussion on probability of error in BF. Application of Bloom Filters to DBs, search engines and P2P. Spectral Bloom Filter and its probability of error. Exercises. | |
| 05/11/24 | Exercises on the topics of the midterm exam | |
| 06/11/24 | Exercises on the topics of the midterm exam | |
| 11/11/24 | MIDTERM EXAM in Rooms C and C1 | Text and solution |
| 12/11/24 | Prefix-free codes, the notion of entropy. Integer coding: the problem and some considerations. Shannon Theorem and optimal codes. The codes Gamma and Delta, space/time performance, and consideration on optimal distributions. Parameterized codes: Rice. | Chap. 11 |
| 13/11/24 | Another parameterized code: PForDelta. Elias-Fano code: definition, properties, and time/space complexity. Definition of Rank/Select operations and comments. Access and NextGEQ operations. Examples on Elias-Fano. | |
| 18/11/24 | Variable-byte code and (s,c)-dense code, with examples. | Python code and slide |
| 19/11/24 | Lab activity with student's laptops on the SDSL library: SDSL installation, the int_vector, vlc_vector, enc_vector, and a sketch of bit-vectors and rank/select ops. | slides 1-24 |
| 20/11/24 | Computing the optimal setting of the parameters in (s,c)-dense codes. Interpolative code. Python code of the algorithms. | Python code |
| 25/11/24 (morning) | Rank and Select: definition and succinct solution for Rank in read-only mode and o(m) space and O(1) time. Succinctly encoding of binary trees. | Chap. 15: 15.1.1 (no Select implementation); 15.1.2 and 15.2.1 |
| 25/11/24 (afternoon) | Exercises on integer codes: gamma, delta, Rice, Interpolation, (s,c)-dense codes, Elias-Fano. | |
| 26/11/24 | How to implement Rank-Select with Elias-Fano and get compressed space. Data Compression. Static, semistatic, and dynamic models for frequency estimation. Huffman (no proof of optimality) and relation to Entropy. Huffman coding: definition, properties and implementation. | Chap. 12: 12.1 (no Lemmas 12.1-12.2, and their proofs). |
| 27/11/24 | Canonical Huffman: definition, properties and implementation. Arithmetic coding: definition, properties and implementation, with proofs of performance. | Sect. 12.1.1, 12.2 all (no 12.5) |
| 02/12/24 | Arithmetic coding: the converter tool and entropy bounds. Dictionary-based compressors: properties and algorithmic structure. LZ77 and LZSS: algorithm, implementation, the issue of the finite window. Exercises | Chap. 13 of the book. gzip and LZ77 and LZSS (13.1) but no LZ78 and LZW. |
| 03/12/2024 | Exercises | |
| 09/12/24, at 11:00, room C | Final term exam |