magistraleinformaticanetworking:ae:ae2014:start
Differenze
Queste sono le differenze tra la revisione selezionata e la versione attuale della pagina.
Entrambe le parti precedenti la revisioneRevisione precedenteProssima revisione | Revisione precedente | ||
magistraleinformaticanetworking:ae:ae2014:start [08/05/2015 alle 06:04 (10 anni fa)] – Paolo Ferragina | magistraleinformaticanetworking:ae:ae2014:start [01/02/2016 alle 08:56 (9 anni fa)] (versione attuale) – [Exam] Paolo Ferragina | ||
---|---|---|---|
Linea 33: | Linea 33: | ||
^ Dates ^ Room ^ Testo ^ | ^ Dates ^ Room ^ Testo ^ | ||
- | | | | text | | + | | 05-06-2015 |
+ | | 29-06-2015 | L1 | {{: | ||
+ | | 20-07-2015 | L1 | {{: | ||
+ | | 10-09-2015 | L1 | {{: | ||
+ | | 11-01-2016 | L1 | {{: | ||
+ | | 01-02-2016 | L1 | {{: | ||
Linea 66: | Linea 71: | ||
| 23/03/2015 | Prefix search: definition of the problem, solution based on arrays, Front-coding, | | 23/03/2015 | Prefix search: definition of the problem, solution based on arrays, Front-coding, | ||
| 24/03/2015 | More on two-level indexing of strings: review of in-memory level based on array of string pointers and uncompacted tries. Solution based on compacted trie and Patricia trie, with analysis of space, I/Os and time of the prefix search. | This year we don't study locality preserving FC. | | | 24/03/2015 | More on two-level indexing of strings: review of in-memory level based on array of string pointers and uncompacted tries. Solution based on compacted trie and Patricia trie, with analysis of space, I/Os and time of the prefix search. | This year we don't study locality preserving FC. | | ||
- | | 25/03/2015 | Randomised data structures: Treaps and Skip lists (with proofs and comments on string items). | [[http:// | + | | 25/03/2015 | Randomised data structures: Treaps and Skip lists (with proofs and comments on string items). | [[http:// |
| | //Students are warmly invited to refresh their know-how about:// hash functions and their properties; hashing with chaining. | Lectures 7 of Demaine-Leiserson' | | | //Students are warmly invited to refresh their know-how about:// hash functions and their properties; hashing with chaining. | Lectures 7 of Demaine-Leiserson' | ||
| 26/03/2015 | Hashing and dictionary problem: direct addessing, simple hash functions, hashing with chaining, uniform hashing and its computing/ | | 26/03/2015 | Hashing and dictionary problem: direct addessing, simple hash functions, hashing with chaining, uniform hashing and its computing/ | ||
Linea 78: | Linea 83: | ||
| 22/04/2015 | Prefix-free codes, notion of entropy, optimal codes. Huffman, with optimality (proof). Canonical Huffman: construction, | | 22/04/2015 | Prefix-free codes, notion of entropy, optimal codes. Huffman, with optimality (proof). Canonical Huffman: construction, | ||
| 23/04/2015 | Exercises | | | | 23/04/2015 | Exercises | | | ||
- | | 27/04/2015 | Arithmetic coding: properties, algorithm and proofs; with examples. | + | | 27/04/2015 | Arithmetic coding: properties, algorithm and proofs; with examples. |
| 28/04/2015 | Dictionary-based compressors: | | 28/04/2015 | Dictionary-based compressors: | ||
| 29/04/2015 | Burrows-Wheeler Transform (forward and backward), Move-To-Front, | | 29/04/2015 | Burrows-Wheeler Transform (forward and backward), Move-To-Front, | ||
| 29/04/2015 | Exercises | | | | 29/04/2015 | Exercises | | | ||
- | | 06/05/2015 | Substring search: definition, properties, reduction to prefix search. The Suffix Array. Binary searching the Suffix Array: p log n (no pages 8.4-8.5). How to compute the lcp-array. Suffix array construction (theo 8.1, but no Skew algorithm, and no Scan-based algorithm). Text mining use of suffix arrays. | + | | 06/05/2015 | Substring search: definition, properties, reduction to prefix search. The Suffix Array. Binary searching the Suffix Array: p log n (no pages 8.4-8.5). How to compute the lcp-array. Suffix array construction (theo 8.1, but no Skew algorithm, and no Scan-based algorithm). Text mining use of suffix arrays. |
| 07/05/2015 | Suffix Trees: properties, structure, pattern search, space occupancy. Construction of Suffix Trees from Suffix Arrays and LCP arrays, and vice versa. LZ77-parsing via suffix trees. | NO McCreight' | | 07/05/2015 | Suffix Trees: properties, structure, pattern search, space occupancy. Construction of Suffix Trees from Suffix Arrays and LCP arrays, and vice versa. LZ77-parsing via suffix trees. | NO McCreight' | ||
| 08/05/2015 | Exercise | | | | 08/05/2015 | Exercise | | | ||
- | | 11/05/2015 | Range-minimum-query over arrays and Lowest common ancestor over trees, reductions and various solutions. Application to k-mismatch problem. | | + | | 11/05/2015 | Range-minimum-query over arrays and Lowest common ancestor over trees, reductions and various solutions. Application to k-mismatch problem. | Read 8.4 of the notes and these {{: |
- | | 12/ | + | | 12/05/2015 | Recap: graphs |
- | | 13/05/2015 | ** ***** NO Lecture ***** ** | | | + | | 18/ |
- | | 14/05/2015 | (EXTRA) Room Seminari EST, hr 9-11 | | | + | | 19/05/2015 | Algorithms for external |
- | | 18/05/2015 | Room N1, hr 11-13 | | | + | | 25/ |
- | | 19/05/2015 | Room C, hr 11-13 | | | + | | 26/05/2015 | Exercises on Graph Problems | |
- | | 20/05/2015 | ** ***** NO Lecture ***** ** | | | + | |
- | | 25/05/2015 | Room N1, hr 11-13 | | | + | |
- | | 26/05/2015 | Room C, hr 11-13 | | | + | |
- | ===== Topics to be dealt with, probably ===== | + | |
- | + | ||
- | + | ||
- | | | + | |
- | | | Minimum Spanning Tree problem: definition, Greedy approach, Kruskal' | + | |
- | | | (Fully) external MST computation. Steiner Tree problem: definition and a 2-approximate solution. Traveling Salesman Tour problem: definition and a 2-approximate solution. | {{: | + |
magistraleinformaticanetworking/ae/ae2014/start.1431065052.txt.gz · Ultima modifica: 08/05/2015 alle 06:04 (10 anni fa) da Paolo Ferragina