*Analisi di algoritmi e complessità*
Dimensione dei dati di un problema. Caso pessimo, ottimo e medio.
*Progettazione di algoritmi*
Paradigma iterativo (Insertionsort). Paradigma divide et impera (Mergesort).
*Ordine di grandezza delle funzioni*
Notazione asintotica.
*Ricorrenze*
Metodi risolutivi. Alberi di ricorsione. Metodo principale.
*Algoritmi di ordinamento: Heapsort*
Heap. Mantenimento delle proprietà dello heap. Costruzione di uno heap. Algoritmo Heapsort. Code con priorità.
*Algoritmi di ordinamento: Quicksort*
Algoritmo Quicksort. Prestazioni di Quicksort. Versione randomizzata di Quicksort. Analisi.
*Ordinamento in tempo lineare*
Limiti inferiori per l'ordinamento. Counting Sort. Radix Sort. Bucket Sort.
*Mediano e selezione*
Minimo e massimo. Selezione con tempo medio lineare.
*Strutture dati fondamentali*
Strutture di base. Realizzazione di puntatori e oggetti. Rappresentazione di alberi radicati.
*Tabelle hash*
Tabelle a indirizzamento diretto. Funzioni hash. Indirizzamento aperto.
*Alberi binari di ricerca*
Operazioni di visita, ricerca, inserimento e cancellazione.
*Programmazione dinamica*
Fasi dello sviluppo di algoritmi. Esempio: ottimizzazione della parentesizzazione per il prodotto di una sequenza di matrici.
*Problemi computazionalmente difficili*
Problemi decisionali, di ricerca e di ottimizzazione. Classi di complessità.