Algoritmi: correttezza, terminazione, complessità (caso pessimo, caso medio). Analisi di InsertionSort. Metodi di progetto: Divide et Impera. Analisi di Ricerca binaria e MergeSort. Fondamenti di Matematica. Principio di Induzione (prova di terminazione e correttezza di programmi). Ordine di grandezza di funzioni: Ο, Ω, θ, ο, ω. Base, tetto, esponenziali, Logaritmi. Sommatorie e serie.

Soluzioni di ricorrenze, verifiche di soluzioni. Il Teorema dell’esperto.

Generalità sugli alberi. Alberi binari (definizione ricorsiva). Rappresentazione con arrays. Heap: procedura di mantenimento dalla proprietà di heap e calcolo della sua complessità. Costruzione di un heap: metodo dal basso e dall’alto, calcolo delle complessità HeapSort e sua complessità. Code di priorità. Inserimento e cancellazione su un heap, complessità. Heaps d-ary.

Ordinamento: Procedure di partizione (3 versioni). Analisi della complessità di QuickSort (caso peggiore, caso migliore, complessità media). Limiti teorici della complessità di ordinamento per confronto. CountingSort. Radix Sort.

Mediana: Complessità di calcolo del minimo e del massimo in una sequenza. La mediana e la selezione dell’i-esimo elemento: algoritmo di complessità media O(n); algoritmo di complessità O(n) nel caso peggiore.

Tabelle hash: Memorizzazione su tabelle con indirizzamento diretto. Collisioni. Tabelle hash. Criteri per funzioni hash. Gestione delle collisioni. Scansione esterna (liste di trabocco). Scansione interna (lineare, quadratica, doppio hashing, pseudocasuale). Cancellazione di dati. Complessità della scansione esterna ed interna senza agglomerati primari.

Alberi di ricerca: Generalità sugli alberi ordinati, realizzazione. Alberi binari di ricerca. Ricerca di chiavi, minimo, massimo, successore e predecessore. Inserimento e cancellazione. Complessità delle operazioni di ricerca e problema del bilanciamento. Alberi binari di ricerca bilanciati. Alberi bilanciati per realizzare insiemi disgiunti (union, find).

Generalità e rappresentazione in memoria. Schema generale di visita di grafi. Alberi di copertura e componenti connesse.Visita in ampiezza (BFS), visita in profondità (DFS) e loro proprietà (classificazione degli archi). Grafi aciclici e ordine topologico (algoritmo con la cancellazione di sorgenti, algoritmo con i tempi di fine-visita DFS). Componenti fortemente connesse (algoritmo con i tempi di fine-visita DFS).