Strumenti Utente
magistraleinformaticanetworking:ae:ae2013:start
Differenze
Queste sono le differenze tra la revisione selezionata e la versione attuale della pagina.
| Entrambe le parti precedenti la revisione Revisione precedente Prossima revisione | Revisione precedente | ||
|
magistraleinformaticanetworking:ae:ae2013:start [13/05/2014 alle 09:36 (10 anni fa)] Paolo Ferragina [Lectures (preliminary schedule)] |
magistraleinformaticanetworking:ae:ae2013:start [08/04/2015 alle 10:53 (9 anni fa)] (versione attuale) Paolo Ferragina [Exam] |
||
|---|---|---|---|
| Linea 34: | Linea 34: | ||
| ^ Dates ^ Room ^ Testo ^ | ^ Dates ^ Room ^ Testo ^ | ||
| - | | | | | | + | | 9 June 2014 | L1 | {{: |
| + | | 30 June 2014 | F | {{: | ||
| + | | 29 July 2014 | L1 | {{: | ||
| + | | 5 November 2014 | hr 9:00 Ferragina' | ||
| + | | 16 January 2015 | hr 9:00, C1 | {{: | ||
| + | | 9 February 2015 | | ||
| + | | 8 April 2015 | hr 11:00, C1 | appello straordinario, | ||
| ====== Background====== | ====== Background====== | ||
| Linea 46: | Linea 53: | ||
| Most of the content of the course will be covered by some notes I wrote in these years; for some topics I'll use parts of papers/ | Most of the content of the course will be covered by some notes I wrote in these years; for some topics I'll use parts of papers/ | ||
| - | ====== Lectures | + | ====== Lectures ====== |
| ^ Date ^ Lecture ^ Biblio ^ | ^ Date ^ Lecture ^ Biblio ^ | ||
| Linea 76: | Linea 83: | ||
| | 16/04/14 | Construction of Suffix Trees from Suffix Arrays and LCP arrays, and vice versa. LZ77-parsing via suffix trees. | NO McCreight' | | 16/04/14 | Construction of Suffix Trees from Suffix Arrays and LCP arrays, and vice versa. LZ77-parsing via suffix trees. | NO McCreight' | ||
| | 28/04/14 | Range-minimum-query over arrays and Lowest common ancestor over trees, reductions and various solutions. Application to k-mismatch problem. | | | | 28/04/14 | Range-minimum-query over arrays and Lowest common ancestor over trees, reductions and various solutions. Application to k-mismatch problem. | | | ||
| - | | 29/04/14 | Burrows-Wheeler Transform (forward and backward), Move-To-Front, | + | | 29/04/14 | Burrows-Wheeler Transform (forward and backward), Move-To-Front, |
| | 30/04/14 | Randomised data structures: Treaps and Skip lists (with proofs). | [[http:// | | 30/04/14 | Randomised data structures: Treaps and Skip lists (with proofs). | [[http:// | ||
| | 05/05/14 | Hashing and dictionary problem: direct addessing, simple hash functions, hashing with chaining, uniform hashing and its computing/ | | 05/05/14 | Hashing and dictionary problem: direct addessing, simple hash functions, hashing with chaining, uniform hashing and its computing/ | ||
| Linea 84: | Linea 91: | ||
| | 12/05/14 | Recap: graphs, BFS and DFS visits, computing shortest-path over unary-length edges. | Chap 22.1, 22.2 and 22.3 of CLR | | | 12/05/14 | Recap: graphs, BFS and DFS visits, computing shortest-path over unary-length edges. | Chap 22.1, 22.2 and 22.3 of CLR | | ||
| | 13/05/14 | Cuckoo hashing: definition, properties, operations with proofs, some algorithm-engineering considerations. | | | | 13/05/14 | Cuckoo hashing: definition, properties, operations with proofs, some algorithm-engineering considerations. | | | ||
| + | | 14/05/14 | Minimal ordered perfect hashing: definition, properties, construction, | ||
| + | | 15/05/14 | Minimum Spanning Tree problem: definition, Greedy approach, Kruskal' | ||
| + | | 20/05/14 | (Fully) external MST computation. Steiner Tree problem: definition and a 2-approximate solution. Traveling Salesman Tour problem: definition and a 2-approximate solution. | {{: | ||
| + | | 22/05/14 | Exercises on MST, Shortest Paths, Steiner Tree problems | | | ||
magistraleinformaticanetworking/ae/ae2013/start.1399973809.txt.gz · Ultima modifica: 13/05/2014 alle 09:36 (10 anni fa) da Paolo Ferragina
Strumenti Pagina
