Algoritmi e Strutture Dati

Lezioni e slide

• Introduzione al corsoPDF
• Capitolo 1: Un’introduzione informale agli algoritmiPDF
• Capitolo 2: Modelli di calcolo e notazione asintoticaPDF
• Capitolo 2: Ricorsione, tecniche di progettazione ed equazioni di ricorrenzaPDF
• Capitolo 4: Ordinare in tempo quadratico: il Selection Sort. Algoritmi di ordinamento che usano la tecnica del divide et impera: MergeSort e QuickSortPDF
• Capitolo 4: Heap SortPDF
• Capitolo 4: un lower bound al problema dell'ordinamento (per una classe ragionevole di algoritmi) e algoritmi lineari (fuori da tale classe di algoritmi)PDF
• Capitolo 3: Strutture dati elementari; rappresentazioni indicizzate e collegate di alberi; algoritmi di visita di alberiPDF
• Capitolo 6: Il problema del Dizionario; Alberi binari di ricerca; alberi AVL PDF
• Capitolo 8: Code con priorita'. d-Heap, Heap Binomiali, (cenni sugli) Heap di Fibonacci PDF
• Grafi. Cosa e perché PDF
• Rappresentazione in memoria di grafi. Visite: ampiezza e profondità PDF
• Applicazioni della visita DFS: cicli, DAG, ordinamento topologico e componenti fortemente connesse PDF
• Cammini minimi in grafi pesati; algoritmo di Dijkstra PDF

Esercitazioni

• Esercitazione 1 · 06/11/25PDF
• Esercitazione 2 · 11/11/25PDF
• Esercitazione 3 · 18/11/25PDF
• Esercitazione 4 · 27/11/25PDF
• Esercitazione 5 · 18/12/25PDF
• Esercitazione 6 · 8/01/26PDF

Problem set

• Problem Set · Istruzioni e consigliPDF
• Template LaTeX per le soluzioniPDFZIP
• Problem Set 1PDF
• Problem Set 2PDF

Diario

Lezioni e slide

• Introduzione al Modulo IIPDF
• Algoritmi greedy: Interval Scheduling e Interval PartitioningPDF
• Strutture dati Union-Find PDF
• Il problema del Minimum Spanning Tree: l'agoritmo di Kruskal e l'algoritmo di Prim; il problema del k-clustering di massimo spacingPDF
• Programmazione Dinamica I: primo esempio e principi generali PDF
• Programmazione Dinamica II: weighted Interval Scheduling, Longest Increasing Subsequence, House Coloring Problem, Segmented Least Squares, Knapsack problem PDF
• Programmazione Dinamica III: sequence alignment, algoritmo di Hirschberg, cammini minimi in grafi con pesi negativi, algoritmo di Bellman-Ford PDF
• Il problema del massimo flusso e il problema del minimo taglio. L'algoritmo di Ford-Fulkerson; teorema del max-flow min-cut; Scegliere buoni cammini aumentantiPDF
• Applicazioni del max-flow. Massimo matching su grafi bipartiti. Massimo numero di cammini arco-disgiunti. Image Segmentation. Baseball elimination PDF
• Introduzione all'NP-completezza. Concetto di riduzione polinomiale. Alcune riduzioni polinomiali PDF
• Ancora sull'NP-completezza. P vs NP. NP-completezza. Co-NP PDF
• Ancora sull'NP-completezza. Qualche altra riduzione. Super Mario, Peg Solitaire e Tetris sono NP-completiPDF
• Algoritmi di approssimazione. Algoritmo 2-apx per Load Balancing. Un algoritmo migliore: 3/2-apx per Load BalancingPDF
• Algoritmi di approssimazione. Algoritmo 2-apx per il problema del k-CenterPDF
• Tabelle hashPDF

Esercitazioni

• Esercitazione 1 · 17/03/26 PDF
• Esercitazione 2 · 31/03/26 PDF
• Esercitazione 3 · 14/04/26 PDF
• Esercitazione 4 · 28/04/26 PDF
• Esercitazione 5 · 12/05/26 PDF

Problem set

• Problem Set 3 PDF

Diario