| Entrambe le parti precedenti la revisioneRevisione precedenteProssima revisione | Revisione precedente |
| digitalhealth:ad2da2024:start [09/07/2024 alle 14:06 (8 mesi fa)] – Paolo Ferragina | digitalhealth:ad2da2024:start [11/09/2024 alle 13:06 (6 mesi fa)] (versione attuale) – [Lectures (TO BE CHANGED SIGNIFICANTLY)] Paolo Ferragina |
|---|
| **Language:** English. | **Language:** English. |
| |
| **Question time:** Monday: 15-17, or by appointment (also in video-conferencing through the [[|virtual room]] of the course) | **Question time:** Monday: 15-17, or by appointment (also in video-conferencing through the [[https://teams.microsoft.com/l/channel/19%3AO9q8qIxe1smcUr3YbVZI9kI3unDQJ7qv4nOkoymbcy41%40thread.tacv2/General?groupId=65581510-815c-49a3-8c9f-ab8ebf19087d|virtual room]] of the course) |
| |
| **News:** about this course will be distributed via a [[ | Telegram channel]]. | **News:** about this course will be distributed via a [[https://t.me/+pS8ExdytXdMwOGI0| Telegram channel]]. |
| |
| **Official lectures schedule:** The schedule and content of the lectures are available below and with the [[https://unimap.unipi.it/registri/dettregistriNEW.php?re=::::&ri=9142|official registro]]. | **Official lectures schedule:** The schedule and content of the lectures are available below and with the [[https://unimap.unipi.it/registri/dettregistriNEW.php?re=::::&ri=9142|official registro]]. |
| 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. | 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. |
| |
| The content of the course will be mainly covered by the book published by //Cambridge University Press// as [https://www.cambridge.org/core/books/pearls-of-algorithm-engineering/95061352D7263CCCBD4F243018236EB2|Pearls of Algorithm Engineering]. | The content of the course will be covered in part by the book published by //Cambridge University Press// as [https://www.cambridge.org/core/books/pearls-of-algorithm-engineering/95061352D7263CCCBD4F243018236EB2|Pearls of Algorithm Engineering], and in part by notes and GitHub refs that will provide the materials of hands-on sessions. |
| |
| |
| |
| |
| The lectures below include also some **EXTRA** material, which is suggested to be read for students aiming to high rankings. | |
| |
| ^ Date ^ Lecture ^ Biblio ^ | ^ Date ^ Lecture ^ Biblio ^ |
| | | Introduction to the course. The definition of Algorithm and time/space complexity. Models of computation: RAM, 2-level memory. An example of algorithm analysis (time, space and I/Os): the sum of n numbers. | Chap. 01 of the book. \\ 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. | | | | Key issues about I/Os, streaming, and hierarchical memory in managing massive datasets. | | |
| | | //Students are warmly invited to read Chapter 2 of the book to refresh their notions about time complexity evaluation// | | | | | Algorithmic and data structure issues concerning atomic versus variable-length items. | | |
| | | Another example of I/Os-analysis: binary search. The B-tree (or B+-tree) data structure: searching and updating a big set of sorted keys. The role of the Virtual Memory system. RAM algorithm for Permuting. The question: sorting vs permuting, comments on the time and I/O bounds. | Chap. 05 of the book. | | | | Two fundamental tools: sorting and permuting. | | |
| | | Permuting algorithm via sorting and scanning, and its I/O-bound. Binary merge-sort, and its I/O-bounds. Snow Plow, with complexity proof and an example. | Chap. 05 of the book | | | | Key-value stores: From basic to advanced hash tables and tries. | | |
| | | //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]] | | | | Textual search engines: compressing and accessing posting lists (integer sequences) and text collections. Deduplicating similar/equal texts, clustering text collections. | | |
| | | Multi-way mergesort: algorithm and I/O-analysis. Lower bound for sorting: comparisons and I/Os. The case of D>1 disks: non-optimality of multi-way MergeSort, the disk-striping technique. \\ **EXTRA:** Lower bound for permuting (sect 5.2.2). | Chap. 05 of the book | | | | Bio-Informatics engines: compressing and indexing arbitrary text for substring search, exact or approximate. | | |
| | | 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. Bounded Quicksort. Multi-way Quicksort: definition, design, and I/O-complexity. | Chap. 05 of the book | | | | Vector DBs: nearest neighbor search, hamming, or Euclidean distance. | | |
| | | Selection of k-1 "good pivot" via Oversampling. 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. | Chap. 05 and Chap. 03 of the book | | | | Advanced storage: Streaming and random access to compressed raw files, time series, and (labeled) graphs. | | |
| | | Reservoir sampling: Algorithm and proofs. Exercises on Random Sampling. Randomized data structures: Treaps with their query (search a key, 3-sided range query). | Chap. 03 of the book. [[http://didawiki.di.unipi.it/lib/exe/fetch.php/magistraleinformaticanetworking/ae/ae2011/04_ericksonnotes-treap-sl.pdf|Notes]] on Treaps. | | |
| | | More on Treaps: update (insert, delete, split, merge) operations (with time complexity and proofs). | Study Theorems and Lemmas in Treaps' notes. | | |
| | | Randomized data structures: Skip lists (with proofs and comments on time-space complexity and I/Os). String sorting: comments on the difficulty of the problem on disk, lower bound. | See Demaine's lecture [[http://videolectures.net/mit6046jf05_demaine_lec12/|num. 12]] on skip lists. String sorting in Chap. 07 of the book. | | |
| | | LSD-radix sort with proof of time complexity and correctness. MSD-radix sort and the trie data structure. | Chap. 07 of the book. | | |
| | | Multi-key Quicksort: algorithm and analysis. Ternary search tree. Exercises. | | | |
| | | Interpolation Search. Fast set intersection, various solutions: scan, sorted merge, binary search, mutual partition. A lower bound on the number of comparisons. | Chap. 06 of the book. See sect. 9.3 for interpolation search.| | |
| | | //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 | | |
| | | Fast set intersection: Exponential jumps, and two-level scan. Hashing and dictionary problem: direct addressing, simple hash functions, hashing with chaining. Global rebuilding technique. | Chap. 08 of the book. | | |
| | | Universal hashing (definition and properties). Three examples of Universal Hash functions, one with correctness proof. The "power of two choices" result. | All theorems with proof, except Theo 8.3 without proof (only the statement). | | |
| | | Cuckoo hashing (with all proofs). | Don't read Perfect Hash (hence no sect. 8.4). | | |
| | | Minimal ordered perfect hashing: definition, properties, construction, space, and time complexity. Exercises. | | | |
| | | Bloom Filter: properties, construction, query and insertion operations, error estimation (with proofs). Application of Bloom Filters to DBs and P2P. \\ **EXTRA:** Lower bound on BF space | No compressed BF. | | |
| | | Prefix search: definition of the problem, solution based on arrays, Front-coding, two-level indexing based on compacted tries. Analysis of space, I/Os, and time of all described solutions. | Chap. 09 (sect. 9.1 and 9.4) of the book. No Locality Preserving front coding. | | |
| | | Exercises | | | |
| | | Exercises. Two-level indexing based on Patricia Trees, with exercises. | | | |
| | | Exercises | | | |
| | | **MIDTERM exam in room ** | .| | |
| | | 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.\\ **EXTRA:** Use of the LCP array to achieve p + log n in the substring search (after Lemma 10.1, up to Lemma 10.2) | Chap. 10 of the book: lemma 10.1 and sect. 10.2.3 (but no "The skew algorithm", no "The Scan-based algorithm"). | | |
| | | Suffix trees: properties, construction from Suffix Arrays and LCP array. Search and mining algorithms over suffix arrays and suffix trees. Exercises | Sect. 10.4.4 (text mining) | | |
| | | Review of the Midterm exam | | | |
| | | 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. The codes Rice, PForDelta. | Chap. 11 of the book. | | |
| | | Elias-Fano code: definition, properties, and time/space complexity. Definition of Rank/Select operations and comments. Access and NextGEQ operations. Examples on Elias-Fano. | | | |
| | | Variable-byte code and (s,c)-dense code, with examples. Interpolative code. Various exercises on all integer coders. | | | |
| | | Rank and Select: definition and succinct solution for Rank. Two theorems: one for a compact solution and one for a compressed solution based on Elias-Fano. \\ **EXTRA:** Solution for Select.| Chap. 15 of the book | | |
| | | Succinctly encoding of binary trees, and labeled binary trees, with examples. | | | |
| | | Data Compression. Static, semistatic, and dynamic models for frequency estimation. Huffman, with optimality (proof) and relation to Entropy. Canonical Huffman: construction, properties. Huffman decompression. | Chap. 12 of the book. No PPM. | | |
| | | Arithmetic coding: properties, the converter tool. Compression, decompression, and entropy bounds. | | | |
| | | Exercises on Huffman and Arithmetic coding, and on succinct binary trees. | | | |
| | | Dictionary-based compressors: properties and algorithmic structure. LZ77, LZSS, LZ78. | Chap. 13 of the book. No LZW. {{ :magistraleinformaticanetworking:ae:ae2021:lect_lz77-78_no_lzw_.ppt |Slides}}. | | |
| | | Compressor bzip: MTF, RLE0, Wheeler-code, Burrows-Wheeler Transform. How to construct the BWT via qsort. How to invert the BWT. | Chap. 14 of the book, and {{ :magistraleinformaticanetworking:ae:ae2023:lect_bwt.pptx |slides}}. | | |
| | | Exercises | | | |
| | | **FINAL TERM exam in room ** | .| | |
