Descrizione generale del corsoVengono presentate e analizzate, anche mediante la tecnica dell'analisi ammortizzata, diverse strutture dati avanzate (quali B-tree, splay tree, heap binomiali e heap di Fibonacci) e le procedure per la loro gestione. Inoltre vengono studiati, progettati e analizzati algoritmi su grafi per la soluzione efficiente di svariati problemi di ottimizzazione.PROGRAMMA PARTICOLAREGGIATO DEL CORSOAnalisi ammortizzataStack con multipop e contatore binarioMetodi dell'aggregazione, degli accantonamenti e del potenzialeTabelle dinamiche con inserimenti e cancellazioniStrutture dati avanzateB-alberi: applicazioni, altezza, ricerca, inserimenti e cancellazioniSplay trees: ricerca, inserimenti e cancellazioni, analisi ammortizzata di m operazioni di cui n sono inserimenti; top-down splay treesStrutture dati per insiemi disgiunti: unione per ranghi, compressione dei cammini, algoritmo Union-Find, notazione di Knuth, funzione di Ackermann e sua inversaHeap binomiali: alberi binomiali, operazioni di inserimento, minimo ed estrazione del minimo, decremento di una chiave, cancellazione di una chiave, unione di due heap binomialiHeap di Fibonacci: alberi binomiali non ordinati, operazioni di inserimento, minimo ed estrazione del minimo, decremento di una chiave, cancellazione di una chiave, unione di due heap di Fibonacci, analisi ammortizzataCammini minimi da una singola sorgente in grafi orientatiGrafo dei cammini minimi, albero dei cammini minimi, algoritmo generico per i camminimi minimi da singola sorgente, algoritmo di Bellman-Ford, algoritmo di Dijkstra, algoritmo lineare su grafi acicliciCammini minimi tra tutte le coppie di nodi in grafi orientatiAlgoritmo di Floyd-Warshall, chiusura transitiva, algoritmo di Johnson su grafi sparsiAlberi ricoprenti minimiPassi rossi e passi blu, invariante del colore, algoritmi di Boruvka, di Kruskal e di Prim, clustering di massima separazioneReti di flusso e applicazioniFlusso reale e flusso netto in una rete di flusso, proprietà del flusso netto, reti con sorgenti e pozzi multipli, notazione di sommatoria implicita, il metodo di Ford-Fulkerson, capacità e rete residue, cammini aumentanti, tagli in reti di flusso, teorema del massimo flusso/minimo taglio, analisi della procedura di Ford-Fulkerson, abbinamento massimo in grafi bipartiti, algoritmo di Edmonds-Karp e sua analisi di complessità, edge-connectivity.

Il libro di testo consigliato è:T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein. Introduction to algorithms (Third Edition), The MIT Press, Cambridge - Massachusetts, 2009disponibile anche nella traduzione italiana1) T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein. Introduzione agli algoritmi e strutture dati 3/ed, McGraw-Hill Italia, 2010.Altra fonte:2) M.A. Weiss. Data structures and algorithmic analysis in C (Second Edition), Addison-Wesley, 1996.