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 [12/05/2015 alle 10:51 (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 ^ | ||
| - | | 05-06-2015 | room L1, hr **** | text | | + | | 05-06-2015 | L1 | no participants |
| - | | 29-06-2015 | room L1, hr 9:00 | text | | + | | 29-06-2015 | L1 | {{:magistraleinformaticanetworking: |
| - | | 20-07-2015 | room L1, hr 9:00 | text | | + | | 20-07-2015 | L1 | {{: |
| + | | 10-09-2015 | L1 | {{: | ||
| + | | 11-01-2016 | L1 | {{: | ||
| + | | 01-02-2016 | L1 | {{: | ||
| Linea 68: | 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 84: | Linea 87: | ||
| | 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. | Read 8.4 of the notes and these {{: | | 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/05/2015 | Recap: graphs and their representations, | | 12/05/2015 | Recap: graphs and their representations, | ||
| - | | 18/ | + | | 18/05/2015 | Minimum Spanning Tree problem: definition, Greedy approach, Kruskal' |
| - | | 19/05/2015 | Room C, hr 11-13 | | | + | | 19/05/2015 | Algorithms for external |
| - | | 25/05/2015 | Room N1, hr 11-13 | | | + | | 25/ |
| - | | 26/05/2015 | Room C, hr 11-13 | | | + | | 26/05/2015 | Exercises on Graph Problems | |
| - | ===== Topics to be dealt with, probably ===== | + | |
| - | + | ||
| - | + | ||
| - | | | + | |
| - | | | (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.1431427893.txt.gz · Ultima modifica: 12/05/2015 alle 10:51 (10 anni fa) da Paolo Ferragina