| Entrambe le parti precedenti la revisioneRevisione precedenteProssima revisione | Revisione precedente |
| magistraleinformaticanetworking:ae:ae2015:start [10/05/2016 alle 09:00 (9 anni fa)] – Paolo Ferragina | magistraleinformaticanetworking:ae:ae2015:start [12/01/2017 alle 21:15 (8 anni fa)] (versione attuale) – [Exam] Paolo Ferragina |
|---|
| \\ | \\ |
| |
| | **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 | |
| |
| |
| | 09/05/16 | Topological sort. Minimum Spanning Tree problem: definition, Greedy approach. | Other {{:magistraleinformaticanetworking:ae:ae2013:mst-clr.pdf|chap on MST 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 | Kruskal's and Prim's algorithms, proof of correctness, semi-external version, analysis of time/IO complexity. A running example. | | | | 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: Shortest Path problem: Dijkstra's algorithm. Algorithms for external and semi-external computation of MST. | A part of the {{:magistraleinformaticanetworking:ae:ae2014:mst-mehlhorn.pdf|Mehlhorn-Sander's book}}, look at Sect 11.5. | | | 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: Also use of MST for clustering and for the bottleneck shortest path problem (no proof). 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. | | | 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 | | | |
