Analisi di algoritmi (12 ore) Algoritmi e strutture dati: generalità ed esempi. Introduzione alla nozione di costo (tempo e spazio di memoria). Notazioni asintotiche per le funzioni di costo e metodi di analisi (caso peggiore, medio, migliore). Metodi di analisi di algoritmi ricorsivi: iterativo, sostituzione, relazione di ricorrenza, Master Theorem. Tipi di dato astratto (12 ore) Tipi di dato astratto (pile, code, alberi) e loro implementazioni. Algoritmi di visita di un albero. Ordinamento (12 ore) Algoritmi di ordinamento incrementali (descrizione, implementazione e analisi): SelectionSort, InsertionSort, BubbleSort, HeapSort. Algoritmi di ordinamento con approccio divide et impera: MergeSort, QuickSort. Lower bound sul costo dell'ordinamento per modello basato su confronti. Algoritmi di ordinamento lineari (descrizione, implementazione e analisi): IntegerSort, BucketSort, RadixSort. Dizionario (6 ore) Tipo di dato Dizionario. Alberi di ricerca binari. Alberi AVL. Tabelle di Hash (6 ore) Grafi (12 ore) Grafi e loro rappresentazione. Algoritmi di visita (descrizione, implementazione e costo). Tecnica algoritmica golosa (greedy). Minimo albero ricoprente e rispettivo calcolo basato su algoritmo greedy. Algoritmi di Kruskal, di Prim e di Boruvka. Cammini minimi su grafi e relativi algoritmi (descrizione, implementazione e analisi): calcolo delle distanze, algoritmo di Bellman e Ford, calcolo dei cammini minimi a sorgente singola su grafi aciclici, algoritmo di Dijkstra.

C. Demetrescu, I. Finocchi, G. F. Italiano: Algoritmi e strutture dati, McGraw-Hill, seconda edizione