INGEGNERIA DEGLI ALGORITMI (seconda parte)
INFORMAZIONI GENERALI
	Obiettivi del corso: approfondire le tematiche sviluppate nella prima metà del corso a livello implementativo e sperimentale, usando Java come linguaggio di riferimento.
	Anno del corso: secondo.
	Lezioni: aula 3NE, lunedì 14:00-15:30, mercoledì 9:30-11:00, giovedì 11:30-13:00.
	Ricevimento: a fine lezione o nel mio ufficio (D1-12) su appuntamento.
	Testi: Progetto di Algoritmi e Strutture Dati in Java, C. Demetrescu, U. Ferraro Petrillo, I. Finocchi, G. F. Italiano, McGraw-Hill. Manuale Java consigliato: Fondamenti di Java, H. Schildt, McGraw-Hill.
	Modalità d'esame: sviluppo in piccoli gruppi di un progetto, e discussione dello stesso su base individuale. I dettagli del progetto saranno forniti durante il corso.I voti conseguiti nella prima e seconda metà del corso faranno media, e risulteranno in un unico voto finale. Per gli studenti che hanno già verbalizzato ASD in passato, sarà possibile verbalizzare il voto conseguito nella seconda metà del corso come "Laboratorio di Programmazione".
	Modalità di frequenza: facoltativa ma fortemente consigliata.
	Modalità d'erogazione: frontale.
	Voti: sono disponibili qui le proposte di voto (non ancora verbalizzate)
PROGRAMMA
	Cenni su Java: tipi di dato ed operatori; istruzioni di controllo; classi, oggetti e metodi; ereditarietà; pacchetti e interfacce; eccezioni; utilizzo dell'I/O.
	Algoritmi e loro Implementazione: analisi dei requisiti, classificazione del problema; sviluppo di un algoritmo, analisi teorica di correttezza e prestazioni; implementazione, collaudo, analisi sperimentale, messa a punto.
	Strutture Dati Elementari: tipo di dato ed interfaccia; strutture dati e classi; strutture indicizzate e collegate; pile e code; dizionari.
	Alberi: preliminari; alberi binari; vettore padri e vettore posizionale; puntatori ai figli, lista di figli, primo figlio-fratello successivo; visite in ampiezza e profondità.
	Ordinamento: insertionsort, selectionsort, bubblesort; mergesort; heap ed heapsort; quicksort; integersort e radixsort.
	Selezione: heapselect; quickselect randomizzatto; quickselect deterministico
	Alberi di Ricerca: alberi binari di ricerca; alberi AVL.
	Tabelle Hash: tabelle ad accesso diretto; tecniche di hashing; liste di collisione; indirizzamento aperto.
	Code con Priorità: heap binari; heap binomiali.
	Union-Find: quickfind; quickunion; bilanciamento della union; compressione durante la find.
	Grafi: preliminari; liste di archi; liste di adiacenza; matrice di adiacenza; matrice di incidenza; visite in ampiezza e profondità.
	Minimo Albero Ricoprente: algoritmo di Kruskal; algoritmo di Prim.
	Cammini Minimi: algoritmo di Bellmann, Ford e Moore; algoritmo di Dijkstra; algoritmo di Floyd e Warshall.
MATERIALE DIDATTICO
Slides:
	cap0: struttura del corso
	cap1: introduzione
	cap2: strutture dati elementari
	cap3: alberi
	cap4: ordinamento
	cap5: selezione
	cap6: alberi di ricerca
	cap7: tavole hash
	cap8: code con priorità
	cap9: union-find
	cap10: grafi
	cap11: spanning tree
	cap12: cammini minimi
Codice (modificato 28/01/10): Il codice verrà inserito gradualmente. Vi prego di segnalarmi eventuali errori/problemi.
	ESEMPI: Hello, Variabili, Operatori, ControlloIfElse, ControlloSwitch, ControlloFor, ControlloWhile, ControlloBreakContinue, Classi1, Classi2, Classi3, Vettori, Interfaccia1, Ereditarieta1, Ereditarieta2, Eccezioni1, Pacchetti1, Studente7, Studente8, provaRandom, provaRandom2.
	LISTE: Record, ListaCollegata, ListaCollegataDemo, RecordDoppio, ListaDoppiamenteCollegata, ListaDoppiamenteCollegataDemo, ListaArray, ListaArrayDemo, ListaArrayDoubling, ListaArrayDoublingDemo.
	CODE: Coda, CodaListaCollegata, CodaListaCollegataDemo, CodaArray, CodaArrayDemo.
	PILE: Pila, PilaListaCollegata, PilaListaCollegataDemo, PilaArray, PilaArrayDemo, PilaArrayDoubling, PilaArrayDoublingDemo, PilaConfrontoDemo.
	DIZIONARI: Dizionario, Coppia, DizionarioArrayOrdinato, DizionarioArrayOrdinatoDemo, DizionarioArrayDoublingOrdinato, DizionarioArrayDoublingOrdinatoDemo, DizionarioListaDisordinata, DizionarioListaDisordinataDemo, DizionarioConfrontoDemo.
	ORDINAMENTO: Ordinamento, selectionSortDemo, insertionSortDemo, bubbleSortDemo, mergeSortDemo, quickSortDetDemo, quickSortDetDemo2, quickSortRandDemo, HeapMax, HeapMaxDemo, heapSortDemo, radixSortDemo, OrdinamentoConfrontoDemo, OrdinamentoConfrontoDemo2, OrdinamentoConfrontoDemo3.
	SELEZIONE: Selezione, sortSelectDemo, trivialSelectDemo, HeapMin, heapSelectDemo, quickSelectDetDemo, quickSelectRandDemo, SelezioneConfrontoDemo, SelezioneConfrontoDemo2, SelezioneConfrontoDemo3.
	ALBERI: NodoListaFigli, AlberoListaFigli, AlberoListaFigliDemo, NodoArrayFigli, AlberoArrayFigli, AlberoArrayFigliDemo, NodoBinario, AlberoBinario, AlberoBinarioDemo
	ALBERI DI RICERCA: DizionarioAlberoRicerca, DizionarioAlberoRicercaDemo, DizionarioAlberoAVL, DizionarioAlberoAVLDemo, DizionarioAlberiConfronto
	TABELLE HASH: DizionarioIndirizzamentoDiretto, DizionarioIndirizzamentoDirettoDemo, FunzioneHash, FunzioneHashMetodoDivisione, FunzioneHashMetodoRipiegamento, FunzioneHashDemo, DizionarioTabellaHashListeCollisione, DizionarioTabellaHashListeCollisioneDemo, FunzioneHashDoppia, FunzioneHashDoppiaScansioneLineare, FunzioneHashDoppiaScansioneQuadratica, FunzioneHashDoppiaHashingDoppio,FunzioneHashDoppiaDemo, DizionarioTabellaHashIndirizzamentoAperto, DizionarioTabellaHashIndirizzamentoApertoDemo, DizionarioTabellaHashIndirizzamentoApertoDemo2
	CODE CON PRIORITA': CodaPriorita, CodaPrioritaHeapBinario, NodoHeapBinario, CodaPrioritaHeapBinarioDemo, CodaPrioritaHeapBinomiale, HeapBinomiale, NodoHeapBinomiale, CodaPrioritaHeapBinomialeDemo
	UNION-FIND: UnionFind, NodoUnionFind, NodoUnionFindBilanciato, UnionFindQuickFind, UnionFindQuickFindDemo, UnionFindQuickFindBilanciato, UnionFindQuickFindBilanciatoDemo, UnionFindQuickUnion, UnionFindQuickUnionDemo, UnionFindQuickUnionBilanciato, UnionFindQuickUnionBilanciatoDemo, UnionFindQuickUnionCompressione, UnionFindQuickUnionCompressioneDemo
	GRAFI: Grafo, Nodo, Arco, GrafoListaAdiacenza, GrafoListaAdiacenzaDemo, GrafoMatriceAdiacenza, GrafoMatriceAdiacenzaDemo.
	ALBERI RICOPRENTI: SpanningTree, SpanningTreeKruskalDemo, SpanningTreePrimDemo.
	CAMMINI MINIMI: CamminiMinimi, CamminiMinimiBellmanDemo, CamminiMinimiDijkstraDemo, CamminiMinimiFloydWarshallDemo.
Progetto: vi prego di segnalarmi eventuali errori e punti poco chiari Progetto Steiner
NEWS
	Le lezioni inizieranno in modo regolare lunedì 30/11/09.
	La lezione del 09/11/09 non si terrà. Se necessario, verrà recuperata verso fine corso.
	Come annunciato in classe, l'esame consiste nella consegna di un progetto in gruppi formati da un minimo di una persona e un massimo di tre persone. Il progetto è costituito da una relazione e dal codice sviluppato. La relazione deve contenere una descrizione teorica del problema e degli algoritmi utilizzati, una descrizione accurata delle scelte implementative (che faciliti la comprensione del codice) e una descrizione degli esperimenti svolti con relativi risultati (grafici etc.) e analisi degli stessi. L'argomento del progetto verrà comunicato a lezione. I progetti vanno consegnati nel periodo dal 08/02/2010 al 14/02/2010. Il progetto va consegnato via email (non occorre iscriversi all'esame). L'email deve contenere il pdf della relazione, il codice e nomi e indirizzi email dei membri del gruppo (in modo da potervi contattare in caso di problemi). La verbalizzazione del progetto avverrà il giorno 17/02/2010 nel mio ufficio (D1-12) a partire dalle 10:00.
	Le lezioni dal 18/01 al 21/01 non si terranno.
	Per poter verbalizzare il voto complessivo di chi sosterrà la prima parte dell'esame (con il Prof. Italiano) nel secondo appello, la data di verbalizzazione è posticipata dal 17/02/2010 al 02/03/2010, stessa ora e stesso luogo. Inoltre, la finestra temporale per la consegna del progetto è posticipata nella settimana dal 15/02/2010 al 21/02/2010.
	Sia il mio voto che quello del Prof. Italiano vengono mantenuti fino a Settembre. La verbalizzazione della media dei due voti avviene però congiuntamente, e me ne occupo sempre io (nelle date che fisso per la verbalizzazione).
	I voti dell'appello del 02/03/2010 sono disponibili qui.
	Il progetto (codice + relazione) per l'appello estivo va consegnato via email nel periodo 01/07/2010-08/07/2010. Ricordate di indicare gli indirizzi email di tutti i membri del gruppo. La discussione del progetto (con relativa verbalizzazione) si terrà il 12/07/2010, alle 10:00, nel mio ufficio (D1-12).
	Mi è stato segnalato che lo scritto della prima parte dell'esame avverrà in parallelo alla discussione del progetto. Gli studenti che sosterranno lo scritto nella mattina, possono discutere il progetto (lo stesso giorno) nel mio ufficio alle 14:00. Le modalità della consegna del progetto non cambiano. Fisserò in seguito un'ulteriore data per la verbalizzazione.
	E' possibile verbalizzare il voto di Ingegneria degli Algoritmi (prima+seconda parte) il 21/07/2010 alle 10:00 nel mio ufficio (D1-12)
	Il progetto (codice + relazione) per l'appello di Settembre va consegnato via email nel periodo 13/09/2010-17/09/2010 (non prima). Ricordate di indicare gli indirizzi email di tutti i membri del gruppo. La discussione del progetto (con relativa verbalizzazione) si terrà il 21/09/2010, alle 10:00, nel mio ufficio (D1-12).
	ATTENZIONE: La discussione del progetto è anticipata al 20/09/2010.