| Entrambe le parti precedenti la revisioneRevisione precedenteProssima revisione | Revisione precedente |
| magistraleinformaticanetworking:ae:ae2011:start [28/03/2012 alle 13:53 (13 anni fa)] – [List of Lectures] Paolo Ferragina | magistraleinformaticanetworking:ae:ae2011:start [15/10/2012 alle 09:32 (13 anni fa)] (versione attuale) – [Exam] Paolo Ferragina |
|---|
| |
| |
| | ====== Exam ====== |
| | |
| | |
| | ^ Dates ^ Room ^ |
| | | 08/06/2012 | {{:magistraleinformaticanetworking:ae:ae2011:ae120608.doc|Text}} | |
| | | 28/06/2012 | {{:magistraleinformaticanetworking:ae:ae2011:ae120628.doc|Text}} | |
| | | 23/07/2012 | {{:magistraleinformaticanetworking:ae:ae2011:ae120723.doc|Text}} | |
| | | 03/09/2012 | {{:magistraleinformaticanetworking:ae:ae2011:ae120903.doc|Text}} | |
| ====== Background====== | ====== Background====== |
| |
| | 08/03/12 | Quicksort: How to bound the memory consumption in the recursive calls. Multi-way Quicksort. Disk striping and comments on the difficulty to use D parallel disks in sorting. Sorting strings: some preliminary considerations, lower bound, MSD-radix sort and its trie implementation. | | | | 08/03/12 | Quicksort: How to bound the memory consumption in the recursive calls. Multi-way Quicksort. Disk striping and comments on the difficulty to use D parallel disks in sorting. Sorting strings: some preliminary considerations, lower bound, MSD-radix sort and its trie implementation. | | |
| | 13/03/12 | Sorting strings: LSD-radix sort, Multi-way Quicksort. | {{{{:magistraleinformaticanetworking:ae:ae2011:lect4-new.pdf|Chap. 5}} of the notes. | | | 13/03/12 | Sorting strings: LSD-radix sort, Multi-way Quicksort. | {{{{:magistraleinformaticanetworking:ae:ae2011:lect4-new.pdf|Chap. 5}} of the notes. | |
| | 15/03/12 | Prefix search for strings: Array of pointers, Front-coding, Locality-preserving FC, Compacted trie, Patricia Trie, two-level indxing. | {{:magistraleinformaticanetworking:ae:ae2011:lect5.pdf|Chap. 6}} of the notes. | | | 15/03/12 | Prefix search for strings: Array of pointers, Front-coding, Locality-preserving FC, Compacted trie, Patricia Trie, two-level indexing. | {{:magistraleinformaticanetworking:ae:ae2011:lect5.pdf|Chap. 6}} of the notes. | |
| | 16/03/12 | Front-coding andd rear coding. Full-text indexing: suffix array, lcp array, text mining with SA, suffix tree. | {{:magistraleinformaticanetworking:ae:ae2011:00.trie-sast.ppt|Slides}} of the lecture. String B-tree is optional. {{:magistraleinformaticanetworking:ae:ae2011:lect6.pdf|Chap 7}} which contains much more material, but you have to read only what has been done in class. | | | 16/03/12 | Front-coding and rear coding. Full-text indexing: suffix array, lcp array, text mining with SA, suffix tree. | {{:magistraleinformaticanetworking:ae:ae2011:00.trie-sast.ppt|Slides}} of the lecture. String B-tree is optional. {{:magistraleinformaticanetworking:ae:ae2011:lect6.pdf|Chap 7}} which contains much more material, but you have to read only what has been done in class. | |
| | 22/03/12 | Suffix array construction: The Skew algorithm. The Bloom filter and its applications | {{:magistraleinformaticanetworking:ae:ae2011:02.bf.ppt|Slides}} and {{:magistraleinformaticanetworking:ae:ae2011:02_bloomfiltersurvey.pdf|paper}} on the BF. | | | 22/03/12 | Suffix array construction: The Skew algorithm. The Bloom filter and its applications | {{:magistraleinformaticanetworking:ae:ae2011:02.bf.ppt|Slides}} and {{:magistraleinformaticanetworking:ae:ae2011:02_bloomfiltersurvey.pdf|paper}} on the BF. | |
| | 27/03/12 | Hashing: hash table with chaining, issues in the use of simple hash functions, universal hashing - definition and examples. | | | | 27/03/12 | Counting/Spectral Bloom filter. Hashing: hash table with chaining, issues in the use of simple hash functions, universal hashing - definition and examples. | | |
| | 29/03/12 | Perfect hashing, cuckoo hashing, d-left hashing. | {{:magistraleinformaticanetworking:ae:ae2011:01._hashing.pptx|Slides}}, {{:magistraleinformaticanetworking:ae:ae2011:01_clr-hash.pdf|CLR chapter}}, {{:magistraleinformaticanetworking:ae:ae2011:01_appoggiomg-minordhash.pdf|part of WMB}} and {{:magistraleinformaticanetworking:ae:ae2011:01_cuckooundergrad.pdf|Cuckoo}}.| | | 29/03/12 | Perfect hashing, cuckoo hashing, d-left hashing, min-ordered perfect hashing. | {{:magistraleinformaticanetworking:ae:ae2011:01._hashing.pptx|Slides}}, {{:magistraleinformaticanetworking:ae:ae2011:01_clr-hash.pdf|CLR chapter}}, {{:magistraleinformaticanetworking:ae:ae2011:01_appoggiomg-minordhash.pdf|part of WMB}} and {{:magistraleinformaticanetworking:ae:ae2011:01_cuckooundergrad.pdf|Cuckoo}}.| |
| | | 12/04/12 | Data Compression: entropy, prefix-free coding, Huffman coding with proof of optimality. | {{:magistraleinformaticanetworking:ae:ae2011:03_mg-compress.pdf|chapter of WMB}}, pag 21-41, 52-56, 74-79. | |
| | | 17/04/12 | Canonical Huffman, Arithmetic Coding | | |
| | | 19/04/12 | Integer Encoding: gamma, delta, Rice, Variable byte, (s,c)-dense codes, PForDelta | {{:magistraleinformaticanetworking:ae:ae2011:chap8.pdf|Chap 8}}, no "interpolative coding" | |
| | | 24/04/12 | Dictionary-based compressors: LZ77, gzip. An example of application: Rsync. Streaming compressors: MTF, RLE. | {{:magistraleinformaticanetworking:ae:ae2011:datacompression.pptx|Slides}} | |
| | | 26/04/12 | Burrows-Wheeler Transform and Bzip | | |
| | | 03/05/12 | Randomized data structures: Treaps | {{:magistraleinformaticanetworking:ae:ae2011:04_ericksonnotes-treap-sl.pdf|some notes}} | |
| | | 10/05/12 | Skip Lists | | |
| | | 15/05/12 | Exercises | | |
| | | 17/05/12 | Exercises | | |
| | | 22/05/12 | Exercises | | |
| | | 24/05/12 | Exercises | | |
