1) Introduzione al corso (lez. 2 ore): Concetto di algoritmo, descrizione e valutazione di algoritmi
2) Introduzione al linguaggio C++ (lab. 2 ore)
3) Nozioni di base (lez. 4 ore): Sommatorie, insiemi, relazioni, grafi, calcolo combinatorio, crescita delle funzioni.
4) Iterazione, induzione e ricorsione (lez. 6, es. 4): iterazione, dimostrazioni induttive, induzione semplice e completa, correttezza e terminazione dei programmi.
5) Analisi di algoritmi (lez. 8, es. 4): tempo di calcolo, ricorrenze e metodi di soluzione (metodo di sostituzione, metodo dell’esperto e metodo dell’albero di ricorsione, efficienza degli algoritmi e algoritmi di ordinamento, analisi ammortizzata (metodo dell’aggregazione, metodo degli accantonamenti, metodo del potenziale).
6) Tipi di dato e strutture di dati elementari (lez. 2, lab. 2): liste, pile, code
7) Alberi (lez. 12, lab. 7): alberi ordinati, alberi binari, algoritmi di visita, alberi binari di ricerca, alberi bilanciati.
8) Tabelle hash (lez. 2, lab. 1)
9) Insiemi e dizionari (lez. 2, lab. 1)
10) Grafi (lez. 12, lab. 7): definizioni, specifica, memorizzazione, visita in ampiezza, visita in profondità e relative applicazioni.
11) Strutture dati avanzate (lez. 2, lab. 2): code con priorità, heap, insiemi disgiunti
12) Introduzione alle tecniche di progettazione di algoritmi (lez. 2)
13) Algoritmi per cammini minimi su grafi (lez. 4, lab. 2): algoritmi di Dijkstra, Johnson, Fredman-Tarjan, Bellman-Ford-Moore
14) La tecnica "Divide et impera" (lez. 4, lab. 1): generalità, ricerca binaria e ricerca per interpolazione, algoritmo quicksort, applicazioni (moltiplicazione di polinomi, moltiplicazione di matrici)
15) Introduzione alla programmazione dinamica (lez. 4, lab. 2): problemi dello string matching approssimato, insieme indipendente di intervalli pesati, cammini minimi, problema dello zaino.
16) Il metodo Greedy (lez. 3, lab. 1): generalità, problema dello zaino reali, problema dell’insieme indipendente di intervalli, minimo albero di copertura, algoritmi di Kruskal e Prim.
17) Ricerca locale (lez. 3, lab. 1): generalità, problema del flusso massimo, algoritmo di Ford-Fulkerson.
18) Backtrack (lez. 2, lab. 1)
19) Algoritmi probabilistici (lez. 2, lab. 1)
20) Problemi intrattabili e relative tecniche risolutive (lez. 4, lab. 1)