Sillabo dell'insegnamento

• A - Fondamenti
COM - Complessità
+ AL-BA - Basic Analysis
Ordine di grandezza. Limite superiore ed inferiore. Strumenti matematici: principio di induzione,
COM - Complessità
+ AL-BA - Basic Analysis
Complessità  intrinseca di un problema.
* CAL - Calcolabilità
+ AL-BACC - Basic Automata, Computability and Complexity
Cenni sui problemi decisionali. La classe P e NP. Soluzioni enumerative.
• B - Algoritmi
* A - Algoritmi fondamentali
+ AL-FDA - Fundamental Data Structures and Algorithms
InsertionSort: analisi della complessità in tempo e spazio nel caso pessimo e nel caso medio.
* A - Algoritmi fondamentali
+ AL-FDA - Fundamental Data Structures and Algorithms
Quicksort con analisi della complessita' in tempo nel caso pessimo e nel caso medio.
* A - Algoritmi fondamentali
+ AL-FDA - Fundamental Data Structures and Algorithms
Visite dei grafi: visita in ampiezza (BFS), visita in profondità  (DFS) e loro proprietà  (classificazione degli archi).
* SDF - Strutture di Dati Fondamentali
+ AL-FDA - Fundamental Data Structures and Algorithms
Code, Pile: operazioni di base
* SDF - Strutture di Dati Fondamentali
+ AL-FDA - Fundamental Data Structures and Algorithms
Generalità  sugli alberi ordinati, realizzazione. Complessità  delle operazioni di visita e di ordinamento utilizzando alberi binari di ricerca. Grafi:generalità  e rappresentazione in memoria. Schema generale di visita di grafi. Alberi di copertura e componenti connesse.
TAPA - Tecniche fondamentali di Analisi e Progetto di Algoritmi
+ AL-AS - Algorithmic Strategies
Divide-et-Impera: Mergesort, Ricerca Binaria, Selezione. Mediana e statistiche d'ordine.
TAPA - Tecniche fondamentali di Analisi e Progetto di Algoritmi
+ AL-AS - Algorithmic Strategies
Greedy: Alberi di copertura di costo minimo: algoritmo di Kruskal, algoritmo di Prim,
TAPA - Tecniche fondamentali di Analisi e Progetto di Algoritmi
+ AL-AS - Algorithmic Strategies
Programmazione dinamica: moltiplicazione di matrici con il minimo numero di prodotti, problema dello zaino intero con/senza
SDA - Strutture di Dati Avanzate
AL-ADSAA - Advanced Data Structures, Algorithms, and Analysis
Cenni su heap binomiali, heap di Fibonacci e strutture dati per UnionFind.
* ASC - Algoritmi su Strutture Combinatorie
+ AL-FDA - Fundamental Data Structures and Algorithms
Grafi aciclici e ordine topologico (algoritmo con la cancellazione di sorgenti, algoritmo con i tempi di fine-visita DFS).
* ASC - Algoritmi su Strutture Combinatorie
+ AL-FDA - Fundamental Data Structures and Algorithms
Cammini minimi da sorgente singola: Bellman Ford, metodo anologo alla moltiplicazione matrice-vettore
* ASC - Algoritmi su Strutture Combinatorie
+ AL-FDA - Fundamental Data Structures and Algorithms
Cammini minimi fra tutte le coppie: algoritmo di Floyd-Warshall, algoritmo analogo alla moltiplicazione di matrici, algoritmo di Johnson per grafi sparsi. Longest Common Subsequence.