| Entrambe le parti precedenti la revisioneRevisione precedenteProssima revisione | Revisione precedente |
| magistraleinformaticanetworking:ae:ae2017:start [28/11/2017 alle 08:05 (7 anni fa)] – [Exam] Paolo Ferragina | magistraleinformaticanetworking:ae:ae2017:start [04/09/2018 alle 07:24 (6 anni fa)] (versione attuale) – [Exam] Paolo Ferragina |
|---|
| |
| ^ Dates ^ Room ^ Text ^ | ^ Dates ^ Room ^ Text ^ |
| | 30/10/2017, hr 9-11 | C1 | Midterm exam: {{ :magistraleinformaticanetworking:ae:ae2017:ae171030.doc |text}}, {{ :magistraleinformaticanetworking:ae:ae2017:ae-compitino1.pdf |results}} (visione compiti a lezione, 6 nov)| | | 30/10/2017, hr 9-11 | C1 | Midterm exam: {{ :magistraleinformaticanetworking:ae:ae2017:ae171030.doc |text}}, {{ :magistraleinformaticanetworking:ae:ae2017:ae-compitino1.pdf |results}} | |
| | 18/12/2017, hr 9-11 | C1 | Finalterm exam: text | | | 18/12/2017, hr 9-11 | C1 | Finalterm exam: {{ :magistraleinformaticanetworking:ae:ae2017:ae171218.doc |text}}, {{ :magistraleinformaticanetworking:ae:ae2017:secondo_compitino.pdf |results}} (visione compiti giorni 19-21 dicembre 2017 ore 10-12. Registrazione in the dates of the following written exams.), {{ :magistraleinformaticanetworking:ae:ae2017:soluzione_-_secondo_compitino_ae.pdf |soluzione}} | |
| | 15/01/2018, hr 14 | C1 | Exam: text | | | 15/01/2018, hr 14 | C1 | Exam: {{ :magistraleinformaticanetworking:ae:ae2017:ae180115.doc |text}} | |
| | 15/02/2018, hr 14 | C1 | Exam: text | | | 15/02/2018, hr 14 | C1 | Exam: {{ :magistraleinformaticanetworking:ae:ae2017:ae180215.doc |text}} | |
| | | 15/06/2018, hr 09-11 | L1 | Exam: {{ :magistraleinformaticanetworking:ae:ae2017:ae180615.doc |text}} | |
| | | 16/07/2018, hr 09-11 | L1 | Exam: {{ :magistraleinformaticanetworking:ae:ae2017:ae180716.doc |text}} | |
| | | 04/09/2018, hr 09-13 | E | Exam: {{ :magistraleinformaticanetworking:ae:ae2017:ae180904.doc |text}} | |
| |
| |
| |
| |
| ====== Lectures (preliminary schedule and links) ====== | ====== Lectures ====== |
| |
| ^ Date ^ Lecture ^ Biblio ^ Slides ^ | ^ Date ^ Lecture ^ Biblio ^ Slides ^ |
| |09/11/2017 | Bloom Filter: properties, construction, query operation (with proofs). Lower bound on BF-like data structures. Randomized data structures: Treaps (with 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. | | |09/11/2017 | Bloom Filter: properties, construction, query operation (with proofs). Lower bound on BF-like data structures. Randomized data structures: Treaps (with 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. | |
| |13/11/2017 | Randomized data structures: Skip lists (with proofs and comments on I/Os). | Study also Theorems and Lemmas. see Demaine's lecture [[http://videolectures.net/mit6046jf05_demaine_lec12/|num. 12]] on skip lists.| | |13/11/2017 | Randomized data structures: Skip lists (with proofs and comments on I/Os). | Study also Theorems and Lemmas. see Demaine's lecture [[http://videolectures.net/mit6046jf05_demaine_lec12/|num. 12]] on skip lists.| |
| | | Please find here the {{ :magistraleinformaticanetworking:ae:ae2017:full_notes.pdf |full set of notes}} | | | | | Please find here the {{ :magistraleinformaticanetworking:ae:ae2017:main_2.pdf |full set of notes}} | | |
| |14/11/2017 | Prefix search: definition of the problem, solution based on arrays, Front-coding, two-level indexing. Locality Preserving front coding and its use with arrays. | Chap. 9 of the notes: 9.1, 9.3. | | |14/11/2017 | Prefix search: definition of the problem, solution based on arrays, Front-coding, two-level indexing. Locality Preserving front coding and its use with arrays. | Chap. 9 of the notes: 9.1, 9.3. | |
| |15/11/2017 | Compacted tries. Analysis of space, I/Os and time of the prefix search for all data structures seen in class. More on two-level indexing of strings: Solution based on Patricia trie, with analysis of space, I/Os and time of the prefix search. Locality Preserving front coding and its use with Patricia trie.| Chap. 9 of the notes: 9.4 and 9.5. | | |15/11/2017 | Compacted tries. Analysis of space, I/Os and time of the prefix search for all data structures seen in class. More on two-level indexing of strings: Solution based on Patricia trie, with analysis of space, I/Os and time of the prefix search. Locality Preserving front coding and its use with Patricia trie.| Chap. 9 of the notes: 9.4 and 9.5. | |
| |22/11/2017 | The k-mismatch problem with SA+LCP or ST and RMQ data structure. Auto-completion search. RMQ and LCA queries, equivalence and reductions, their algorithmic solutions and few applications. | Sect 10.4.1 | | |22/11/2017 | The k-mismatch problem with SA+LCP or ST and RMQ data structure. Auto-completion search. RMQ and LCA queries, equivalence and reductions, their algorithmic solutions and few applications. | Sect 10.4.1 | |
| |23/11/2017 | Exercises | | | |23/11/2017 | Exercises | | |
| |27/11/2017 | No lecture | | | |28/11/2017 | Prefix-free codes, notion of entropy, optimal codes. Integer coding: the problem and some considerations. The codes Gamma and Delta, space/time performance and consideration on optimal distributions. Rice, PForDelta. | Chap. 11 of the notes | |
| |28/11/2017 | | | | |29/11/2017 | Coders: (s,c)-codes, variable-byte, Interpolative. Elias-Fano. With examples. | | |
| |29/11/2017 | | | | |30/11/2017 | Huffman, with optimality (proof). | Chap. 12 of the notes (no sect 12.1.2). | |
| |04/12/2017 | | | | |04/12/2017 | Canonical Huffman: construction, properties, decompression algorithm. Arithmetic coding: properties, algorithm and proofs; with examples. | No PPM and Range coding. | |
| |05/12/2017 | | | | |05/12/2017 | No lecture | | |
| |06/12/2017 | | | | |06/12/2017 | Dictionary-based compressors: properties and algorithmic structure. LZ77, LZSS and gzip. LZ8 and LZW. LZ parsing with suffix trees and LCA queries. | {{ :magistraleinformaticanetworking:ae:ae2017:datacompression_-_completo.pptx |Slides}}\\ Chap 13, no par 13.4, and Chap 10 at sect 10.4.2 | |
| |11/12/2017 | No lecture | | | |06/12/2017 | Burrows-Wheeler Transform (forward and backward), Move-To-Front (with proof of entropy bound), Run-Length-Encoding, bzip2. | Chap. 14 of the notes. Do not study sections 14.4 and 14.5. | |
| |12/12/2017 | No lecture | | | |13/12/2017 | Exercises on data compression. | | |
| |13/12/2017 | | | | |
| | |
| | |
| | |
| | | Prefix-free codes, notion of entropy, optimal codes. Integer coding: the problem and some considerations. The codes Gamma and Delta, space/time performance and consideration on optimal distributions. Rice, PForDelta. | Chap. 11 of the notes | | |
| | | Coders: (s,c)-codes, variable-byte, Interpolative. With examples. | | | |
| | | Example on Interpolative and Elias-Fano. | | | |
| | | Huffman, with optimality (proof). Canonical Huffman: construction, properties, decompression algorithm. | Chap. 12 of the notes (no sect 12.1.2). | | |
| | | Arithmetic coding: properties, algorithm and proofs; with examples. | No PPM and Range coding. | | |
| | | Dictionary-based compressors: properties and algorithmic structure. LZ77, LZSS and gzip. LZ8 and LZW. LZ parsing with suffix trees and LCA queries. | Chap 13, no par 13.4, and Chap 10 at sect 10.4.2 | | |
| | | Burrows-Wheeler Transform (forward and backward), Move-To-Front, Run-Length-Encoding, bzip2. | Chap. 14 of the notes. Do not study Theorem 14.5 and sections 14.4 and 14.5.| | |
| | | Exercises on data compression. | | | |
