| Entrambe le parti precedenti la revisione
Revisione precedente
Prossima revisione
|
Revisione precedente
|
magistraleinformaticanetworking:ae:ae2015:start [05/05/2016 alle 11:46 (8 anni fa)]
Paolo Ferragina [Lectures] |
magistraleinformaticanetworking:ae:ae2015:start [12/01/2017 alle 21:15 (7 anni fa)] (versione attuale)
Paolo Ferragina [Exam] |
| \\ | \\ |
| |
| | **Student meetings June-July - Ferragina's office**: June 3 (hr 9-11), June 13 (hr 9-11) and June 21 (hr 9-11). In July it will be by appointment (send email to me). |
| ====== Goals ====== | ====== Goals ====== |
| |
| |
| ^ Dates ^ Room ^ Testo ^ | ^ Dates ^ Room ^ Testo ^ |
| | 6 June 2016, hr 9:00 | L1 | | | | 6 June 2016, hr 9:00 | L1 | no participants | |
| | 27 June 2016, hr 14:00 | L1 | | | | 27 June 2016, hr 14:00 | L1 | {{:magistraleinformaticanetworking:ae:ae2015:ae160627.doc|text}} | |
| | 19 July 2016, hr 9:00 | L1 | | | | 19 July 2016, hr 9:00 | L1 | {{:magistraleinformaticanetworking:ae:ae2015:ae160719.doc|text}} | |
| | | 2 September 2016, hr 9:30 | L1 | {{:magistraleinformaticanetworking:ae:ae2015:ae160902.doc|text}} | |
| | | 12 January 2017, hr 9:00 | L1 | {{:magistraleinformaticanetworking:ae:ae2015:ae170112.doc|text}} | |
| | | 3 February 2017, hr 9:00 | L1 | text | |
| |
| |
| | 03/05/16 | LZ parsing with suffix trees and LCA queries. Exercises on tries, suffix trees and suffix arrays. | | | | 03/05/16 | LZ parsing with suffix trees and LCA queries. Exercises on tries, suffix trees and suffix arrays. | | |
| | 05/05/16 | Recap: graphs and their representations, BFS and DFS visits, computing shortest-path over unary-length edges. | {{:magistraleinformaticanetworking:ae:ae2014:clr-graphs.pdf|Chap 23.1-23.3}} of CLR. Do not study Lemma 23.5. | | | 05/05/16 | Recap: graphs and their representations, BFS and DFS visits, computing shortest-path over unary-length edges. | {{:magistraleinformaticanetworking:ae:ae2014:clr-graphs.pdf|Chap 23.1-23.3}} of CLR. Do not study Lemma 23.5. | |
| | 09/05/16 | lecture 9-11 in room C -- Topological sort e altro | Chap 23.4 of CLR | | | 09/05/16 | Topological sort. Minimum Spanning Tree problem: definition, Greedy approach. | Other {{:magistraleinformaticanetworking:ae:ae2013:mst-clr.pdf|chap on MST of CLR}} | |
| | 10/05/16 | lecture 9-11 in room L1 | | | | 10/05/16 | Kruskal's and Prim's algorithms, proof of correctness, semi-external version, analysis of time/IO complexity. A running example. | | |
| | 12/05/16 | lecture 9-11 in room N1 | | | | 12/05/16 | Shortest Path problem: Dijkstra's algorithm. Algorithms for external and semi-external computation of MST. | For Shortest Path look at this [[https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm|note]]. For external MST, look at Sect 11.5 of the {{:magistraleinformaticanetworking:ae:ae2014:mst-mehlhorn.pdf|Mehlhorn-Sander's book}}. | |
| | 19/05/16 | lecture 9-11 in room N1 | | | | 19/05/16 | Use of MST for clustering and for the bottleneck shortest path problem (no proof). The case of negative edges in Shortest Path problem: Bellman-Ford's algorithm. How to detect a negative cycle in a directed graph. | Few {{:magistraleinformaticanetworking:ae:ae2015:15shortestpaths.pdf|slides}} on BF-algorithm | |
| | 23/05/16 | lecture 9-11 in room L1 | | | | 23/05/16 | Exercises on graphs | | |
| | 24/05/16 | lecture 9-11 in room N1 | | | |
| | |
| | |
| ====== Possible topics for this year's course (to be updated) ====== | |
| | |
| | | | |
| | | Minimum Spanning Tree problem: definition, Greedy approach, Kruskal's and Prim's algorithms. | {{:magistraleinformaticanetworking:ae:ae2013:mst-clr.pdf|Chap 23 of CLR}} | | |
| | | Algorithms for external and semi-external computation of MST. Also use of MST for clustering and for the bottleneck shortest path problem (no proof). | A part of the {{:magistraleinformaticanetworking:ae:ae2014:mst-mehlhorn.pdf|Mehlhorn-Sander's book}}, look at Sect 11.5. | | |
| | | Shortest Path problem: Dijkstra's algorithm. Steiner Tree problem: definition and a 2-approximate solution. Traveling Salesman Tour problem: definition and a 2-approximate solution. | Part of the {{:magistraleinformaticanetworking:ae:ae2013:clr_-_sp.pdf|chap on Shortest Path of CLR}}. Also {{:magistraleinformaticanetworking:ae:ae2012:mst-mehlhorn.pdf|sect 11.5 and 11.6}} of Sanders-Mehlhorn's book. | | |
