| Prossima revisione | Revisione precedente |
| magistraleinformaticanetworking:ae:ae2024:start [22/05/2024 alle 14:43 (10 mesi fa)] – creata Paolo Ferragina | magistraleinformaticanetworking:ae:ae2024:start [11/09/2024 alle 06:20 (6 mesi fa)] (versione attuale) – [Algorithm Engineering A.A. 2024-2025] 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/team/19%3AXvIFdeKkSQvk3TupfRJlZNgMlOcmWxKxjWzg4hPWjks1%40thread.tacv2/conversations?groupId=a350f200-733a-4760-a152-e5f3c31cabef&tenantId=c7456b31-a220-47f5-be52-473828670aa1|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/+uBZNz93deVA2NmI0| 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 [[|official registro]]. |
| \\ | \\ |
| |
| ^ Week Schedule ^^^ | ^ Week Schedule ^^^ |
| ^ Day ^ Time Slot ^ Room ^ | ^ Day ^ Time Slot ^ Room ^ |
| | Monday | 9:00 - 11:00 | Room Fib | | | Monday | 9:00 - 11:00 | Room Fib C | |
| | Tuesday | 9:00 - 11:00 | Room Fib | | | Tuesday | 9:00 - 11:00 | Room Fib C1 | |
| | Wednesday | 11:00 - 13:00 | Room Fib | | | Wednesday | 9:00 - 11:00 | Room Fib C1 | |
| |
| |
| |
| ^ Dates ^ Room ^ Text ^ Notes ^ | ^ Dates ^ Room ^ Text ^ Notes ^ |
| | 06/11/2023, start at 14:00 | room E | Mid term: [[https://www.dropbox.com/scl/fi/iacfhv1ds8j737x83mvsn/AE231106.pdf?rlkey=g95k0r9hmfd527llxmob0s2qm&dl=0|text]], {{ :magistraleinformaticanetworking:ae:ae2023:ae231106-sol1.pdf |solution}}, {{ :magistraleinformaticanetworking:ae:ae2023:midterm2023.pdf |results}} | | | | 00/00/2024, start at 00:00 | room 00 | text, results | | |
| | 12/12/2023, start at 09:30 | room C | Final term: {{ :magistraleinformaticanetworking:ae:ae2023:ae231212.pdf |text}}, {{ :magistraleinformaticanetworking:ae:ae2023:ae231212-sol.pdf |solution}}, {{ :magistraleinformaticanetworking:ae:ae2023:algorithmengineering-2024_finalterm.pdf |results}} | | | |
| | 15/01/2024, start at 9:00 | room C1 | Exam: {{ :magistraleinformaticanetworking:ae:ae2023:ae240115.pdf |text}}, {{ :magistraleinformaticanetworking:ae:ae2023:ae240115-sol.pdf |solution}}, {{ :magistraleinformaticanetworking:ae:ae2023:algorithmengineering-2024-jan24.pdf |results}} | | | |
| | 09/02/2024, start at 00:00 | room 00 | Exam: {{ :magistraleinformaticanetworking:ae:ae2023:ae240209.pdf |text}}, {{ :magistraleinformaticanetworking:ae:ae2023:ae240209-sol.pdf |solution}}, {{ :magistraleinformaticanetworking:ae:ae2023:ale240209-ris.pdf |results}} | Correction and view of the written exam on Wednesday, 14 February, hr: 17:30 (MS Teams). | | |
| |
| ====== Background and Notes of the Course ====== | ====== Background and Notes of the Course ====== |
| |
| ^ Date ^ Lecture ^ Biblio ^ | ^ Date ^ Lecture ^ Biblio ^ |
| | 18/09/2023 | 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. | | | | 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. | |
| | | //Students are warmly invited to read Chapter 2 of the book to refresh their notions about time complexity evaluation// | | | | | //Students are warmly invited to read Chapter 2 of the book to refresh their notions about time complexity evaluation// | | |
| | 19/09/2023 | 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. | | | | 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. | |
| | 20/09/2023 | 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 | | | | 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 | |
| | | //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]] | | | | //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]] | |
| | 25/09/2023 | 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 | | | | 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 | |
| | 26/09/2023 | 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 | | | | 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 | |
| | 27/09/2023 | 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 | | | | 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 | |
| | 02/10/2023 | 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. | | | | 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. | |
| | 03/10/2023 | More on Treaps: update (insert, delete, split, merge) operations (with time complexity and proofs). | Study Theorems and Lemmas in Treaps' notes. | | | | More on Treaps: update (insert, delete, split, merge) operations (with time complexity and proofs). | Study Theorems and Lemmas in Treaps' notes. | |
| | 04/10/2023 | 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. | | | | 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. | |
| | 09/10/2023 | LSD-radix sort with proof of time complexity and correctness. MSD-radix sort and the trie data structure. | 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. | |
| | 10/10/2023 | Multi-key Quicksort: algorithm and analysis. Ternary search tree. Exercises. | | | | | Multi-key Quicksort: algorithm and analysis. Ternary search tree. Exercises. | | |
| | 11/10/2023 | 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.| | | | 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 | | | | //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 | |
| | 16/10/2023 | 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. | | | | 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. | |
| | 17/10/2023 | 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). | | | | 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). | |
| | 18/10/2023 | Cuckoo hashing (with all proofs). | Don't read Perfect Hash (hence no sect. 8.4). | | | | Cuckoo hashing (with all proofs). | Don't read Perfect Hash (hence no sect. 8.4). | |
| | 23/10/2023 | Minimal ordered perfect hashing: definition, properties, construction, space, and time complexity. Exercises. | | | | | Minimal ordered perfect hashing: definition, properties, construction, space, and time complexity. Exercises. | | |
| | 24/10/2023 | 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. | | | | 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. | |
| | 25/10/2023 | 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. | | | | 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. | |
| | 30/10/2023 | Exercises | | | | | Exercises | | |
| | 31/10/2023 | Exercises. Two-level indexing based on Patricia Trees, with exercises. | | | | | Exercises. Two-level indexing based on Patricia Trees, with exercises. | | |
| | 06/11/2023 | Exercises | | | | | Exercises | | |
| | 06/11/2023 | **MIDTERM exam in room E, 14-16** | Please register [[https://forms.office.com/e/Fihi2iLuXJ|here]] by Nov 1st 2023.| | | | **MIDTERM exam in room ** | .| |
| | 07/11/2023 | 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"). | | | | 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"). | |
| | 08/11/2023 | 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) | | | | 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) | |
| | 13/11/2023 | Review of the Midterm exam | | | | | Review of the Midterm exam | | |
| | 14/11/2023 | 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. | | | | 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. | |
| | 15/11/2023 | Elias-Fano code: definition, properties, and time/space complexity. Definition of Rank/Select operations and comments. Access and NextGEQ operations. Examples on Elias-Fano. | | | | | Elias-Fano code: definition, properties, and time/space complexity. Definition of Rank/Select operations and comments. Access and NextGEQ operations. Examples on Elias-Fano. | | |
| | 20/11/2023 | Variable-byte code and (s,c)-dense code, with examples. Interpolative code. Various exercises on all integer coders. | | | | | Variable-byte code and (s,c)-dense code, with examples. Interpolative code. Various exercises on all integer coders. | | |
| | 21/11/2023 | 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 | | | | 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 | |
| | 22/11/2023 | Succinctly encoding of binary trees, and labeled binary trees, with examples. | | | | | Succinctly encoding of binary trees, and labeled binary trees, with examples. | | |
| | 27/11/2023 | 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. | | | | 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. | |
| | 27/11/2023 | Arithmetic coding: properties, the converter tool. Compression, decompression, and entropy bounds. | | | | | Arithmetic coding: properties, the converter tool. Compression, decompression, and entropy bounds. | | |
| | 28/11/2023 | Exercises on Huffman and Arithmetic coding, and on succinct binary trees. | | | | | Exercises on Huffman and Arithmetic coding, and on succinct binary trees. | | |
| | 04/12/2023 | 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}}. | | | | 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}}. | |
| | 05/12/2023 | 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}}. | | | | 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}}. | |
| | 06/12/2023 | Exercises | | | | | Exercises | | |
| | 11/12/2023 | Exercises | | | | | **FINAL TERM exam in room ** | .| |
| | 12/12/2023 | **FINAL TERM exam in room C, 9:30-11** | Please register in the ESAMI platform, on the exam date of January.| | |
