- Concetti base ricorsione
- Esempi classici ricorsione
- Problema dello zaino
- Equazioni di ricorrenza
- Notazione O
- Notazione
- Notazione
- Notazioni piccole
- Metodo Master
- Heapify (Min e max heapify)
- DecreaseKey
- heapInsert
- extractMax e Min
- BuildMinHeap/BuildMaxHeap
- Heapsort
- Fare esercizi sugli Heap
- Riscrivere gli pseudocodici sugli heap
- Albero di decisione e dimostrazione
- Counting sort
- Radix sort
- Introduzione alle tabelle hash
- Tabelle ad indirizzamento diretto
- Funzioni di hashing (divisione, moltiplicazione)
- Hashing con concatenazione e dimostrazione
- Hashing ad indirizzamento aperto
- Inserimento, ricerca e cancellazione (indirizzamento aperto)
- Requisiti di una buona funzione di hash ad indirizzamento aperto
- Teniche per la creazione di sequenze di ispezione
- Esercizi sulle sequenze di ispezione (ds/generale)
- Alberi bilanciati, degenere e ripasso proprietà BST
- Reppresentazione di un albero rosso nero e definizione altezza nera
- RBT: rotazioni
- RBT: inserimento (regole come ave maria)
- RBT: eliminazione (regole come ave maria)
- RBT: esercizi
- RBT: ignorare pseucodice
- Introduzione alla prog dinamica
- Fibonacc
- RodCut
- Moltiplicazione tra matrici
- Distanza di editing
- Longest Common Substring (Lezione 11)
- Longest Common Subsequence (libro + sottostruttura ottima gemini)
- Introduzione agli algoritmi greedy
- Problema dello zaino
- Activity Selector (appunti + libro)
- Compressione di huffman
- Grafi
- Proprietà dei grafi
- Rappresentazione dei grafi
- BFS
- DFS
- Introduzione alla ricerca dei cammini minimi
- Proprietà dei cammini minimi
- Generic SSSP in un DAG
- Algoritmo di Bellam-Ford
- Algoritmo di Dijkstra
- Programmazione dinamica per la risoluzione dei cammini minimi tra tutte le coppie
- Algoritmo Floyd-Warshall
- Esercizi Floyd Warshall
- Esercizi Dijkstra
- Esercizi bellam ford
Dimostrazioni
- Dimostrazione ricerca con successo (hashing con concatenazione)
- Hashing con indirizzamento aperto (ricerca con successo e senza)
- Dimostrazione altezza nera (pagina 42)
- Dimostrazione sottostruttura ottima (RODCUT)
- Dimostrazione sottostruttura ottima LCS e LCS
- Dimostrazione sottostruttura ottima EDT
- Dimostrazione sottostruttura ottima Huffman
- Dimostrazione scelta greedy Huffman
- Dimostrazione sottostruttura ottima Activity Selector
- Dimostrazione scelta greedy Activity Selector
- Dimostrazione sottostruttura ottima Matrix Moltiplication
- Dimostrazione sottostruttura ottima cammini minimi
Da ricordare
- Pseudocodici RODCUT
- Pseudocodici MATRIX
- Pseudocodici LCS e LCS
- Pseudocodici EDT
- Pseudocodici HUFFMAN
- Pseudocodici CountingSort
- Pseudocodici heap
- Pseudocodici BFS
- Pseudocodici DFS
- Pseudocodice SSSP DAG
- Pseudocodice Dijkstra
- Pseudocodice Bellam Ford
- Pseudocide Floyd Warshall
- Pseudocodice APSP
- Casi metodo Master
- Casi rimozione (vengono richiesti anche gli esempi grafici)
- Casi inserimento (vengono richiesti anche gli esempi grafici)