====== Algorithm Engineering A.A. 2021-2022 ======

{{:magistraleinformaticanetworking:ae:ae2011:ae.png?150x150 |Thanks to P. Sanders}} 
**Teacher**: [[http://www.di.unipi.it/~ferragin/|Paolo Ferragina]]

**CFU:** 9 (first semester). 

**Course ID:** 531AA.

**Language:** English.    

**Question time:** Monday: 15-17, or by appointment (given COVID-19 situation, it will occur in video-conferencing within the virtual room of the course)

**News:** about this course will be distributed via a [[https://t.me/CourseALE2021 | Telegram channel]].

**Official lectures schedule:** The schedule and content of the lectures is available below and with the [[https://unimap.unipi.it/registri/dettregistriNEW.php?re=3323820::::&ri=9142|official registro]].
\\


====== Goals ====== 

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, 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 on. 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.

===== Week Schedule of the Lectures =====

^           Week Schedule           ^^^
^  Day  ^  Time Slot  ^  Room  ^
| Monday  |  9:00 - 11:00  | Room Fib A1, and [[https://teams.microsoft.com/l/team/19%3ap-avxz8D5d3hWXIeln74eT3NXKsq-1bJ5vMEm8Z14gU1%40thread.tacv2/conversations?groupId=9f5dd0c3-684b-454f-ad6d-54f058daf55d&tenantId=c7456b31-a220-47f5-be52-473828670aa1|Virtual Room]] of the course | 
| Tuesday  |  11:00 - 13:00  | Room Fib L1, and [[https://teams.microsoft.com/l/team/19%3ap-avxz8D5d3hWXIeln74eT3NXKsq-1bJ5vMEm8Z14gU1%40thread.tacv2/conversations?groupId=9f5dd0c3-684b-454f-ad6d-54f058daf55d&tenantId=c7456b31-a220-47f5-be52-473828670aa1|Virtual Room]] of the course | 
| Wednesday  |  9:00 - 11:00  | Room Fib A1, and [[https://teams.microsoft.com/l/team/19%3ap-avxz8D5d3hWXIeln74eT3NXKsq-1bJ5vMEm8Z14gU1%40thread.tacv2/conversations?groupId=9f5dd0c3-684b-454f-ad6d-54f058daf55d&tenantId=c7456b31-a220-47f5-be52-473828670aa1|Virtual Room]] of the course | 


====== Exam ====== 

The exam will consist of a written test plus an oral discussion. 

As last year, I'm planning to have one midterm exam in November and one in December. The two midterms (if >= 18 as vote) will be combined with an oral exam to be given in January, which can **increase or decrease** the final vote (by few points, given that they will somewhat "average" with the vote reported in the written exam).


^ Dates ^ Room ^ Text ^ Notes ^
| 08/11/2021, start at 09:00 | room A1 and virtual | {{ :magistraleinformaticanetworking:ae:ae2021:ae211108.pdf |text}}, {{ :magistraleinformaticanetworking:ae:ae2021:algorithmengineering-2022-midterm1.pdf |results}}, {{ :magistraleinformaticanetworking:ae:ae2021:ale_2021_11_08_tutto_.pdf |solution}} (Rice-code should use rest from 0)| The **midterm exam** will consist of a set of exercises, and will last for 45mins. The part of the program for the exercises will be detailed in the list of lectures below.  |
| 15/12/2021, start at 09:00 | room C and virtual | {{ :magistraleinformaticanetworking:ae:ae2021:ae211215.pdf |text}}, {{ :magistraleinformaticanetworking:ae:ae2021:results-ale-finalterm21.pdf |results}}, {{ :magistraleinformaticanetworking:ae:ae2021:ae211215_soluzione_.pdf |solution}} | The **FinalTerm exam** will have the same structure as the other one, but can participate only the students who got >=18 rank in the first MidTerm. Students have to register at the [[https://forms.office.com/r/fw1qnEHkR0|following link]] by December 7th, 2021. |
| 14/01/2022, start at 14:00 | room C1 | {{ :magistraleinformaticanetworking:ae:ae2021:ae220114.pdf |text}}, {{ :magistraleinformaticanetworking:ae:ae2021:algoeng-jan2022.pdf |results}}, {{ :magistraleinformaticanetworking:ae:ae2021:ae220114_soluzione_.pdf |solution}} | Oral will start at 16:00, of 14.01.\\ Students can attend the oral exam in the next exam dates too (starting from Feb). |
| 02/02/2022, start at 09:00 | room C1 | {{ :magistraleinformaticanetworking:ae:ae2021:ae220202.pdf |text}}, {{ :magistraleinformaticanetworking:ae:ae2021:ae-ris_feb22.pdf |results}}, {{ :magistraleinformaticanetworking:ae:ae2021:ae220202_soluzione_.pdf |solution}} | Oral will start at 14:30 in the virtual room of the course, the same day of the written exam |
| 13/06/2022, start at 09:00 | room L1 | {{ :magistraleinformaticanetworking:ae:ae2021:ae220613.pdf |text}}, {{ :magistraleinformaticanetworking:ae:ae2021:ae220613_soluzione_.pdf |solution}} |  |
| 04/07/2022 |  | {{ :magistraleinformaticanetworking:ae:ae2021:ae220704_scritto_.pdf |text}} |  |
| 25/07/2022 |  | {{ :magistraleinformaticanetworking:ae:ae2021:ae220725_scritto_.doc |text}} |  |
====== Background and Notes of the Course ====== 

I strongly suggest refreshing your knowledge about basic Algorithms and Data Structures by looking at the well-known book [[https://mitpress.mit.edu/books/introduction-algorithms-third-edition|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 [[http://videolectures.net/mit6046jf05_introduction_algorithms/|Video Lectures]] by Erik Demaine and Charles Leiserson, specifically Lectures 1-7, 9-10, and 15-17.

Most of the content of the course will be covered by some notes I wrote in these years; for some topics, parts of papers/books will be used. You can download the latest version of these notes from [[https://www.cambridge.org/core/books/pearls-of-algorithm-engineering/95061352D7263CCCBD4F243018236EB2|this link]]. I state that **this material** will be published by //Cambridge University Press// as //Pearls of Algorithm Engineering// by me. This prepublication version is free to view and download for personal use only. Not for redistribution, resale or use in derivative works. © Paolo Ferragina 2020.


====== Lectures ====== 

Video-lectures of this year are available below, the ones of the  [[https://web.microsoftstream.com/group/37a1faa2-cf5c-48d7-89e7-c68c57fa6c35|last academic year]] are available too (click on "Videos", and then sort them by name). \\

The lectures below include also some **EXTRA** material, which is suggested to be read for students aiming to high rankings.

^ Date ^ Lecture ^ Biblio ^
| 13/09/2021 | Introduction to the course. Models of computation: RAM, 2-level memory. An example of algorithm analysis: the sum of n numbers, and binary search. The B-tree (or B+-tree) data structure: searching and updating a big-set of sorted keys. Exercise: evaluating the I/O-cost of binary search. | Chap. 1 of the notes. \\ Read [[https://en.wikipedia.org/wiki/B-tree|note 1]] and [[https://www.cs.cmu.edu/~ckingsf/bioinfo-lectures/btrees.pdf|note 2]] on B-trees.\\ video [[https://unipiit.sharepoint.com/sites/a__td_517732/Shared%20Documents/General/Recordings/Lezione%20del%202021-09-13-20210913_091345-Meeting%20Recording.mp4?web=1|part 1]] and [[https://unipiit.sharepoint.com/sites/a__td_517732/Shared%20Documents/General/Recordings/Lezione%20del%202021-09-13-20210913_100730-Meeting%20Recording.mp4?web=1|part 2]] |
| 14/09/2021 | The role of the Virtual  Memory system. Algorithm for Permuting. Sorting atomic items: sorting vs permuting, comments on the time and I/O bounds. Binary merge-sort, and its I/O-bounds.    | Chapter 2 (no sect 2.5-) \\ video [[https://unipiit.sharepoint.com/sites/a__td_517732/Shared%20Documents/General/Recordings/Lezione%20del%202021_09_14-20210914_110605-Meeting%20Recording.mp4?web=1|part 1]] and [[https://unipiit.sharepoint.com/sites/a__td_517732/Shared%20Documents/General/Recordings/Lezione%20del%202021_09_14-20210914_121021-Meeting%20Recording.mp4?web=1|part 2]] |
| 15/09/2021 | Snow Plow, with complexity proof and an example. Multi-way mergesort. The case of D>1 disks: non-optimality of multi-way MergeSort, the disk-striping technique. \\ Finding the maximum-sum subsequence (study from my notes!). | Chap. 5 of the notes.\\ video [[https://unipiit.sharepoint.com/sites/a__td_517732/Shared%20Documents/General/Recordings/Lezione%20del%202021_09_15-20210915_090424-Meeting%20Recording.mp4?web=1|part 1]] and [[https://unipiit.sharepoint.com/sites/a__td_517732/Shared%20Documents/General/Recordings/Lezione%20del%202021_09_15-20210915_100303-Meeting%20Recording.mp4?web=1|part 2]]  |  
|  | //Students are warmly invited to refresh their know-how about://  Divide-and-conquer technique for algorithm design and Master Theorem for solving recurrent relations; and Binary Search Trees | Lecture 2, 9 and 10  of [[http://videolectures.net/mit6046jf05_introduction_algorithms/|Demaine-Leiserson's course at MIT]] |
| 20/09/2021 | Lower bound for sorting: comparisons and I/Os. Quicksort: recap on best-case, worst-case. Quicksort: Average-case with analysis. Selection of kth ranked item in linear average time (with proof). 3-way partition for better in-memory quicksort. RandSelect. \\ **EXTRA:** Lower bound for permuting.   | Chap. 5 of the notes\\ video [[https://unipiit.sharepoint.com/sites/a__td_517732/Shared%20Documents/General/Recordings/Lezione%20del%202021_09_20-20210920_090157-Meeting%20Recording.mp4?web=1|part 1]] and [[https://unipiit.sharepoint.com/sites/a__td_517732/Shared%20Documents/General/Recordings/Lezione%20del%202021_09_20-20210920_101011-Meeting%20Recording.mp4?web=1|part 2]] |
| 21/09/2021 | The dual pivot. Bounded Quicksort. Multi-way Quicksort: definition, design and I/O-complexity. Selection of k-1 "good pivot" via Oversampling. Proof of the average time complexity of Multi-way Quicksort. | Chap. 5 of the notes\\ video [[https://unipiit.sharepoint.com/sites/a__td_517732/Shared%20Documents/General/Recordings/Lezione%20del%202021_09_21-20210921_110247-Meeting%20Recording.mp4?web=1|part 1]] and [[https://unipiit.sharepoint.com/sites/a__td_517732/Shared%20Documents/General/Recordings/Lezione%20del%202021_09_21-20210921_120137-Meeting%20Recording.mp4?web=1|part 2]] |
| 22/09/2021 | Random sampling: disk model, known length (algorithms and proofs). Random sampling on the streaming model, known and unknown length. Reservoir sampling. Algorithm and proofs. | Chap. 3 of the notes. |  
| 27/09/2021 | Exercises on Random Sampling and sorting.\\ Randomized data structures: Treaps  (with time complexity and proofs). | [[http://didawiki.di.unipi.it/lib/exe/fetch.php/magistraleinformaticanetworking/ae/ae2011/04_ericksonnotes-treap-sl.pdf|Notes]] by others.  Study also Theorems and Lemmas.\\ video [[https://unipiit.sharepoint.com/sites/a__td_517732/Shared%20Documents/General/Recordings/Lezione%20del%202021_09_27-20210927_090130-Meeting%20Recording.mp4?web=1|part 1]] and [[https://unipiit.sharepoint.com/sites/a__td_517732/Shared%20Documents/General/Recordings/Lezione%20del%202021_09_27-20210927_100948-Meeting%20Recording.mp4?web=1|part 2]] |
| 28/09/2021 | Randomized data structures: Skip lists (with proofs and comments on time-space complexity and I/Os).   | See Demaine's lecture [[http://videolectures.net/mit6046jf05_demaine_lec12/|num. 12]] on skip lists.\\ video [[https://unipiit.sharepoint.com/sites/a__td_517732/Shared%20Documents/General/Recordings/Lezione%20del%202021_09_28-20210928_110502-Meeting%20Recording.mp4?web=1|part 1]] and [[https://unipiit.sharepoint.com/sites/a__td_517732/Shared%20Documents/General/Recordings/Lezione%20del%202021_09_28-20210928_121105-Meeting%20Recording.mp4?web=1|part 2]] |  
| 29/09/2021 | Fast set intersection, various solutions: scan, sorted merge, binary search, mutual partition, binary search with exponential jumps. Fast set intersection: two-level scan. Interpolation Search. \\ **EXTRA:** random shuffling (sect. 6.4). | Chap. 6 of the notes, and Sect 9.2.\\ video [[https://unipiit.sharepoint.com/sites/a__td_517732/Shared%20Documents/General/Recordings/Lezione%20del%202021_09_29-20210929_090244-Meeting%20Recording.mp4?web=1|part 1]] and [[https://unipiit.sharepoint.com/sites/a__td_517732/Shared%20Documents/General/Recordings/Lezione%20del%202021_09_29-20210929_101328-Meeting%20Recording.mp4?web=1|part 2]] | 
| 06/10/2021 | Prefix-free codes, the notion of entropy. Integer coding: the problem and some considerations.  | Chap. 11 of the notes.\\ From last year: Video [[https://www.dropbox.com/s/ndx2bu3ee8zx8xj/2020-10-14%20ALE%20parte%201.mp4?dl=0|part 1]][[https://www.dropbox.com/s/ozsdbkc2y6h74uz/2020-10-14%20ALE%20parte%202.mp4?dl=0|part 2]] |
| 11/10/2021 | Shannon Theorem and optimal codes. The codes Gamma and Delta, space/time performance, and consideration on optimal distributions. The codes Rice, PForDelta, variable-byte. | Video [[https://unipiit.sharepoint.com/sites/a__td_517732/Shared%20Documents/General/Recordings/Lezione%20del%2020211011-20211011_070624-Meeting%20Recording.mp4|part 1]] and [[https://unipiit.sharepoint.com/sites/a__td_517732/Shared%20Documents/General/Recordings/Lezione%20del%2020211011-20211011_080043-Meeting%20Recording.mp4|part 2]] |
| 12/10/2021 | (s,c)-codes, with examples.  | Video [[https://unipiit.sharepoint.com/sites/a__td_517732/Shared%20Documents/General/Recordings/Lezione%20del%202021_10_12-20211012_111750-Registrazione%20della%20riunione.mp4|part 1]] and [[https://unipiit.sharepoint.com/sites/a__td_517732/Shared%20Documents/General/Recordings/General-20211012_115829-Registrazione%20della%20riunione.mp4|part 2]] |
| 13/10/2021 | Interpolative code. Elias-Fano code. | Video [[https://unipiit.sharepoint.com/sites/a__td_517732/Shared%20Documents/General/Recordings/Lezione%20del%202021_10_13-20211013_090545-Registrazione%20della%20riunione.mp4|part 1]] and [[https://unipiit.sharepoint.com/sites/a__td_517732/Shared%20Documents/General/Recordings/Lezione%20del%202021_10_13-20211013_100640-Registrazione%20della%20riunione.mp4|part 2]] |
| 18/10/2021 | More on Elias-Fano code. Exercises | Video [[https://unipiit.sharepoint.com/sites/a__td_517732/Shared%20Documents/General/Recordings/Lezione%20del%202021_10_18-20211018_090446-Registrazione%20della%20riunione.mp4|part 1]] and [[https://unipiit.sharepoint.com/sites/a__td_517732/Shared%20Documents/General/Recordings/Lezione%20del%202021_10_18-20211018_100239-Registrazione%20della%20riunione.mp4|part 2]] | 
| 19/10/2021 | Exercises on integer coders. [[https://pastebin.com/QVMzukxM|Python code]] for Interpolative coding. | [[https://unipiit.sharepoint.com/sites/a__td_517732/Shared%20Documents/General/Recordings/Lezione%202021_10_19-20211019_111142-Registrazione%20della%20riunione.mp4|Video]] and {{ :magistraleinformaticanetworking:ae:ae2021:documenti_scansionati.pdf |notes of today}}. | 
| 20/10/2021 | {{ :magistraleinformaticanetworking:ae:ae2021:documenti_scansionati_2.pdf |Exercises}} on integer encoders.\\ Lab activity (optional): A gentle introduction to the Succinct Data Structure Library: integer sequences. (Please, prepare in advance the environment for experimenting with the SDSL library, as indicated at the [[https://github.com/gvinciguerra/AE2021-tutorial|repo]].) | [[https://unipiit.sharepoint.com/sites/a__td_517732/Shared%20Documents/General/Recordings/Lezione%202021_10_20-20211020_091334-Registrazione%20della%20riunione.mp4|video]] and {{ :magistraleinformaticanetworking:ae:ae2021:sdsl_a_gentle_introduction.pdf |slides SDSL}} |
| 25/10/2021 | String sorting: comments on the difficulty of the problem on disk, lower bound. LSD-radix sort with proof of time complexity and correctness. MSD-radix sort and the trie data structure. | Chap. 7 of the notes.\\ [[https://unipiit.sharepoint.com/sites/a__td_517732/Shared%20Documents/General/Recordings/Lezione%202021_10_25-20211025_090943-Registrazione%20della%20riunione.mp4|Video]] |
| 26/10/2021 | Multi-key Quicksort. Ternary search tree. Exercises. | [[https://unipiit.sharepoint.com/sites/a__td_517732/Shared%20Documents/General/Recordings/Lezione%20del%2026_10_2021-20211026_111637-Registrazione%20della%20riunione.mp4|Video]] |
| 27/10/2021 | Exercises. | [[https://unipiit.sharepoint.com/sites/a__td_517732/Shared%20Documents/General/Recordings/Lezione%20del%202021_10_27-20211027_091204-Meeting%20Recording.mp4?web=1|Video]] |
| 02/11/2021 | Exercises. | [[https://unipiit.sharepoint.com/sites/a__td_517732/Shared%20Documents/General/Recordings/Lezione%20del%202021_11_02-20211102_111017-Meeting%20Recording.mp4|video]] |
| 03/11/2021 | Exercises. |  |
| 08/11/2021 | **MidTerm Exam** (see above for details, and topics are the ones up to this point in the Agenda). |  |
| 09/11/2021 | Rank and Select: definition and succinct solution for Rank. Compressed solution based on Elias-Fano coding.\\ **EXTRA:** Solution for Select.| Chapter 15 of the notes.\\ [[https://unipiit.sharepoint.com/sites/a__td_517732/Shared%20Documents/General/Recordings/Lezione%20del%202021_11_09-20211109_110316-Meeting%20Recording.mp4?web=1|Video]] |
| 10/11/2021 | Succinctly encoding binary trees, with examples. | Sect. 9.2.\\ [[https://unipiit.sharepoint.com/sites/a__td_517732/Shared%20Documents/General/Recordings/General-20211012_115829-Registrazione%20della%20riunione.mp4|Video]] |
| 15/11/2021 | Data Compression. Static, semistatic and dynamic models for frequency estimation. Huffman, with optimality (proof) and relation to Entropy | Chap. 12 of the notes. No PPM.\\ [[https://unipiit.sharepoint.com/sites/a__td_517732/Shared%20Documents/General/Recordings/Lezione%20del%202021_11_15-20211115_090352-Meeting%20Recording.mp4|video]] |
| 16/11/2021 | Canonical Huffman: construction, properties. Huffman decompression. Arithmetic coding: properties, algorithm and proofs. | [[https://unipiit.sharepoint.com/sites/a__td_517732/Shared%20Documents/General/Recordings/Lezione%20del%202021_11_16-20211116_111346-Meeting%20Recording.mp4?web=1|Video]] |
| 17/11/2021 | Exercises on Statistical coders | {{ :magistraleinformaticanetworking:ae:ae2020:ale-esercizi_su_huffman_e_arithmetic.pdf |notes}}, [[https://unipiit.sharepoint.com/sites/a__td_517732/Shared%20Documents/General/Recordings/Riunione%20in%20_General_-20211117_090545-Registrazione%20della%20riunione.mp4?web=1|Video]] |
| 22/11/2021 | More on Arithmetic coding: decoding, encoding the output, and entropy bounds. Dictionary-based compressors: properties and algorithmic structure. LZ77, LZSS, LZ78.  | Chap 13.1 and 13.2. No LZW. {{ :magistraleinformaticanetworking:ae:ae2021:lect_lz77-78_no_lzw_.ppt |Slides}} and [[https://unipiit.sharepoint.com/sites/a__td_517732/Shared%20Documents/General/Recordings/Lezione%20del%202021_11_22-20211122_090322-Meeting%20Recording.mp4|video]]. | 
| 23/11/2021 | 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. Text mining use of suffix arrays. Compressor bzip: MTF, RLE, Burrows-Wheeler Transform. | Chap. 10 of the notes: 10.1, 10.2.1 (but no page 10-4 and 10-5 and thus no Lemma 10.2), 10.2.3 (but no "The skew algorithm", no "The Scan-based algorithm"), 10.4.3 and 14.1-14.3.\\ [[https://unipiit.sharepoint.com/sites/a__td_517732/Shared%20Documents/General/Recordings/Lezione%20del%202021_11_23-20211123_110530-Meeting%20Recording.mp4?web=1|Video]] and [[https://www.dropbox.com/s/m4yogpojydotw97/Lect%20SA-ST%20and%20Bwt.pptx?dl=0|slides]] |
| 23/11/2021 | Exercises | [[https://unipiit.sharepoint.com/:v:/r/sites/a__td_517732/Shared%20Documents/General/Recordings/Lezione%20del%202021_11_23-20211123_110530-Meeting%20Recording.mp4?csf=1&web=1&e=IDTwHk|Video]] and [[https://www.dropbox.com/s/bcs2va92cb3t9pq/LZ77%2C%20LZss%2C%20LZ78%2C%20Bzip2.pdf?dl=0|notes]] |
| 24/11/2021 | How to construct the BWT via qsort. How to invert the BWT. Exercises. | Video [[https://unipiit.sharepoint.com/sites/a__td_517732/Shared%20Documents/General/Recordings/Lezione%20del%202021_11_24-20211124_090354-Meeting%20Recording.mp4?web=1|part 1]] and [[https://unipiit.sharepoint.com/sites/a__td_517732/Shared%20Documents/General/Recordings/Lezione%20del%202021_11_24-20211124_094243-Registrazione%20della%20riunione.mp4|part 2]]. [[https://www.dropbox.com/s/tiqp6pr9v6aaehg/LZ77%2C%20LZss%2C%20LZ78%2C%20Bzip2.pdf?dl=0|Notes]] on exercises.|
|  | //Students are warmly invited to refresh their know-how about:// hash functions and their properties; hashing with chaining. | Lectures 7 of [[http://videolectures.net/mit6046jf05_introduction_algorithms/|Demaine-Leiserson's course]] at MIT | 
| 29/11/2021 | Hashing and dictionary problem: direct addressing, simple hash functions, hashing with chaining. Uniform hashing and its computing/storage cost, universal hashing (definition and properties). Two examples of Universal Hash functions: one with correctness proof, the other without. | Chap. 8 of the notes. All theorems with proof, except Theo 8.3 and 8.5 without a proof (only the statement).\\ [[https://unipiit.sharepoint.com/sites/a__td_517732/Shared%20Documents/General/Recordings/Lezione%20del%202021_11_29-20211129_090144-Meeting%20Recording.mp4|Video]] |
| 30/11/2021 | Cuckoo hashing (with all proofs). Minimal ordered perfect hashing: definition, properties, construction, space and time complexity. | No Perfect Hash (8.5).\\ [[https://unipiit.sharepoint.com/:v:/r/sites/a__td_517732/Shared%20Documents/General/Recordings/Lezione%20del%202021_11_30-20211130_110513-Meeting%20Recording.mp4?csf=1&web=1&e=I6eKHm|Video]] |
| 01/12/2021 | Bloom Filter: properties, construction, query and insertion operations, error estimation (with proofs). Spectral Bloom Filter. Prefix search: definition of the problem, solution based on arrays, Front-coding, two-level indexing based on compacted tries or Patricia Trees. Analysis of space, I/Os and time of all described solutions. \\ **EXTRA:** Lower bound on BF space | No 8.7.2 (compressed BF). Chap. 9 of the notes: 9.1, 9.4, 9.5. No Locality Preserving front coding (9.3).\\ [[https://unipiit.sharepoint.com/:v:/r/sites/a__td_517732/Shared%20Documents/General/Recordings/Lezione%20del%202021_12_01-20211201_090211-Meeting%20Recording.mp4?csf=1&web=1&e=yibPAd|Video]] |
| 06/12/2021 | Exercises | [[https://unipiit.sharepoint.com/:v:/r/sites/a__td_517732/Shared%20Documents/General/Recordings/Lezione%20del%202021_12_06-20211206_090607-Meeting%20Recording.mp4?csf=1&web=1&e=RoebWH|video]] |
| 07/12/2021 | Exercises | [[https://unipiit.sharepoint.com/sites/a__td_517732/Shared%20Documents/General/Recordings/Lezione%20del%202021_12_07-20211207_111041-Meeting%20Recording.mp4?web=1|Video]] |
| 13/12/2021 | Student meeting - exercises | [[https://unipiit.sharepoint.com/sites/a__td_517732/Shared%20Documents/General/Recordings/Meeting%20del%202021_12_13-20211213_090808-Meeting%20Recording.mp4?web=1|Video]] |
| 15/12/2021 | **FinalTerm exam**. Topics will be the ones that we have dealt with after the MidTerm exam. Students have to register at the [[https://forms.office.com/r/fw1qnEHkR0|following link]] by December 7th, 2021. | |