| Entrambe le parti precedenti la revisioneRevisione precedenteProssima revisione | Revisione precedente |
| magistraleinformaticanetworking:ae:ae2021:start [14/01/2022 alle 18:36 (3 anni fa)] – [Exam] Paolo Ferragina | magistraleinformaticanetworking:ae:ae2021:start [27/04/2023 alle 15:32 (17 mesi fa)] (versione attuale) – [Background and Notes of the Course] Paolo Ferragina |
|---|
| | 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. | | | 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). | | | 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 **TBD** | text, results, solution | | | | 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 ====== | ====== 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. | 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.dropbox.com/s/20zimrhrk2m4frw/Book%20pre-publication.pdf?dl=0|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. | 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. |
| |
| |
| | 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.| | | 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 | | | | //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.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]] | | | 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]] | | | 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]] | | | 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]] | |
