Programma suddiviso per esercitazioni

• E1: Implementazioni dell'adt Lista: sequenziale e dinamica. Realizzazione dei metodi fondamentali: inserisci(posizione, oggetto), cancella(posizione), elemento(posizione), lunghezza().
• E2: Implementazioni dell'adt Pila e adt Coda: sequenziale e dinamica. Realizzazione dei metodi fondamentali:
  • per Pila: top(), pop(), push(oggetto), lunghezza();
  • per Coda: inserisci(oggetto), cancella(), elemento(), lunghezza().
• E3: Implementazioni dell'adt Insieme. Studio implementazione con liste: questione del metodo equals(). Valutazioni costi. Studio costi per implementazione con liste ordinate. Uso della struttura dati Iteratore.
• E3 appendice: Esempio d'uso dell'interfaccia Comparable nell'esercitazione E3.
• E4: Ripasso del concetto di ricorsione.
• E5: Implementazioni dell'adt Albero: vettori paralleli e strutture dinamiche. Operazioni fondamentali: inserisciFiglio(padre, oggetto), cancellaFiglio(padre, oggetto), visita in pre-ordine, post-ordine e in-ordine (limitatamente agli alberi binari). Alberi binari di ricerca: operazioni di visita, inserimento, ricerca e cancellazione.
• E6: Implementazione dell'adt Albero AVL. Definizione e caratteristiche degli alberi AVL. Studio operazioni fondamentali di bilanciamento. Implementazione dell'operazione di inserimento elemento.
• E7: Implementazione dell'adt Hash Table. Studio delle tecniche principali per risolvere le collisioni: chaining, open addressing lineare e open addressing con indirizzamento doppio. Confronto computazionale di tali tecniche. Proprietà fondamentali funzione hash. Tecniche per costruzione funzione hash: divisione, moltiplicazione, folding. Implementazione mediante array.
• E8: Introduzione alla programmazione dinamica. Schema generale di un algoritmo di programmazione dinamica. Esempi di applicazione: determinazione ordine di moltiplicazione di matrici, determinazione massima sottosequenza comune di due stringhe.
• E9: Introduzione allo heap e all'adt coda con priorità. Operazioni fondamentali: inserimento, rimozione, minimo.
• E10: Algoritmi di ordinamento HeapSort e ShellSort.
• E11: Algoritmi di ordinamento MergeSort e QuickSort. Confronto tra le diverse varianti.
• E12: Algoritmi di ordinamento CountingSort, RadixSort e BucketSort.
• E13: Introduzione alla programmazione Greedy: formulazione generale e caratterizzazione classe dei problemi per i quali gli algoritmi greedy forniscono soluzioni ottime (teorema di Rado).
• E14: Implementazione algoritmo di Kruskal per l'albero di copertura minimo.
• E15: Introduzione e implementazione algoritmo di Prim per l'albero di copertura minimo.