Complessità computazionale. Confronto asintotico tra funzioni. Classi O-grande. Proprietà delle classi e algebra di O-grande. Altre nozioni asintotiche: Omega e Theta. Analisi della complessità di un algoritmo: fattorizzazione e test di primalità. Relazioni di ricorrenza.
Iterazione. Il metodo delle asserzioni. Invarianti di ciclo. Contatori ed accumulatori. Algoritmi iterativi: MCD, ordinamento di un vettore per selzione ed inserimento, moltiplicazione alla russa, funzione perno e calcolo della mediana.
Ricorsione. Ricorsione lineare e ad albero. Trasformazione di ricorsioni lineari in ricorsioni di coda. Simulazione della ricorsione mediante una pila. Ricorsione induttiva o ben fondata. Tecniche di programmazione ricorsiva: backtracking e divide et impera. Algoritmi: fattoriale, esponenziale veloce (e sua trasformazione in forma ricorsiva di coda ed iterativa), le torri di Hanoi, generazione delle permutazioni di ordine n, otto regine, ricerca dicotomica, minimo e massimo, ordinamento per fusione (merge sort).
Memoria dinamica. Puntatori. Dereferenziazione. L'operatore indirizzo. I riferimenti. Vettori e puntatori. Passaggio di parametri per valore, riferimento e puntatore. Allocazione dinamica della memoria. Allocazione di un vettore. I record (strutture): loro allocazione ed accesso. Definizione di nuovi tipi: il tipo Vettore e Matrice. Deallocazione.
Le strutture informative. Strutture dati. Le liste: definizione, rappresentazione, algoritmi iterativi e ricorsivi sulle liste: lunghezza, ricerca di un elemento, inserimento, cancellazione, concatenazione, inversione. Insiemi rappresentati con liste ordinate; unione di due liste. Alberi: definizione erappresentazione. Algoritmi elementari sugli alberi: cardinalità ed altezza. Visite di un albero: DFS e BFS. Alberi binari di ricerca (BST); algoritmi di ricerca, inserimento e cancellazione su un BST.
ADT e classi. Nozione di "tipo di dato astratto". Specifica sintattica e semantica. Astrazione ed incapsulamento.Strutture dati come realizzazione di ADT: primitive d'accesso, programmazione delle funzioni base, invariante di struttura. Gli oggetti: stato e funzioni membro (metodi). Le classi. Istanziazione di una classe: il costruttore ed il distruttore. Il costruttore di copia. Esempi: razionali, polinomi, matrici.
Nota. La preparazione richiesta comprende una conoscenza del C++ sufficiente per capire e implementare gli algoritmi e le strutture dati o le classi di cui ai punti precedenti.