ALGORITMI E STRUTTURE DATI (ONLINE)
INFORMAZIONI GENERALI
	Obiettivi del corso: fornire strumenti di base per la progettazione e l'analisi formale di algoritmi e strutture dati.
	Collocazione del corso: secondo anno, primo semestre, primo emisemestre (5 crediti).
	Interazione con il docente: domande sulla teoria e/o sugli esercizi possono essere poste via email all'indirizzo grandoni@disp.uniroma2.it. Il docente risponderà il prima possibile, su base individuale o collettiva a seconda dei casi. Il docente è anche disponibile a ricevere gli studenti su appuntamento.
	Testi: Algoritmi e Strutture Dati, C. Demetrescu, I. Finocchi, G. F. Italiano, McGraw-Hill, 2008.
	Modalità d'esame: l'esame consiste nello svolgimento (scritto e/o orale, a seconda del numero di iscritti) di un insieme di esercizi. Un esercizio può essere sia una domanda di natura teorica sui contenuti del corso, sia la richiesta di applicare un dato algoritmo ad un dato input (illustrando i vari passaggi).
	Modalità di frequenza: gli studenti hanno la possibilità (non l'obbligo) di seguire le lezioni frontali con il Prof. Italiano (consultate il suo sito per orari etc.). E' importante però notare che il corso frontale può differire leggermente negli argomenti trattati e che l'esame può essere di tipologia piuttosto diversa.
	Modalità d'erogazione: online.
	Voti: sono disponibili qui le proposte di voto (rimuovo periodicamente i voti verbalizzati)
PROGRAMMA
	Modelli di calcolo e metodologie di analisi: notazione asintotica; analisi di caso medio e pessimo; analisi di algoritmi randomizzati; analisi ammortizzata.
	Strutture Dati Elementari: pile e code; rappresentazione e visita di alberi.
	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: rappresentazione; 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 (nella versione stampabile in bianco e nero alcune figure si vedono male):
	cap0 (stampabile): informazioni generali
	cap1 (stampabile): un'introduzione informale agli algoritmi
	cap2 (stampabile): modelli di calcolo e metodologie di analisi
	cap3 (stampabile): strutture dati elementari
	cap4 (stampabile): ordinamento
	cap5 (stampabile): selezione e statistiche di ordine
	cap6 (stampabile): alberi di ricerca
	cap7 (stampabile): tavole hash
	cap8 (stampabile): code con priorità
	cap9 (stampabile): union-find
	cap11 (stampabile): grafi e visite di grafi
	cap12 (stampabile): minimo albero ricoprente
	cap13 (stampabile): cammini minimi
Esercizi svolti: Sotto trovate un esame completo con le relative soluzioni. Tale esame è solo un esempio di massima su come sarà l'esame effettivo. In particolare, quest'ultimo potrà toccare argomenti diversi e avere diversa difficoltà. Vi prego di segnalarmi eventuali errori/problemi.
	Esempio appello
NEWS
	(19/01/2011) Un secondo appello è fissato per il 08/02/2011 (posticipato rispetto ad un precedente annuncio!), alle 11:00 nel mio ufficio (stanza D1-12, nuovi edifici). Per iscriversi a tale appello occorre inviarmi una mail, con le stesse modalità che per il primo appello, il giorno 01/02/2011 entro le 19:00.
	(29/12/2010) L'appello invernale è fissato per il 01/02/2011, alle 11:00 nel mio ufficio (stanza D1-12, nuovi edifici). Per prenotarsi occorre inviare una mail con oggetto del tipo "APPELLO ASD: Nome COGNOME" nella finestra 24/01/2010-30/01/2010.
	(11/11/2010) Ho aggiunto una versione stampabile in bianco e nero delle slide. Vi avverto però che alcune figure si vedono male.
	(27/10/2010) Mi sono accorto che nel sito di Ingegneria Online, non so perché, erano visibili per ASD alcuni dettagli che avevo nascosto (programma, progetto etc.). Si tratta di notizie non aggiornate. Questo ha (giustamente) creato dubbi in alcuni di voi. Ora le vecchie informazioni sono nuovamente invisibili. In futuro, fate riferimento solo alla mia pagina Web.
	Per gli studenti che sul piano di studi hanno ASD da 5 crediti, si verbalizzerà il voto subito dopo l'esame. Per quelli che invece hanno Ingegneria degli Algoritmi da 10 o 9, bisognerà superare, nelle stesse date e con le stesse modalità, l'esame di ASD con me e in più l'esame di Laboratorio di Programmazione con il Prof. Faruolo. La media dei voti di ASD e LabProg verrà verbalizzata come un unico esame (da me o dal Prof. Faruolo) una volta superate entrambe le prove (volendo in sessioni diverse).
	Il capitolo 10 del libro non è parte del programma. Per il resto, dovete studiare tutti gli argomenti fino al capitolo 13 (anche se non compaiono sulle slide).
	Rispondendo ad una domanda comune: potete utilizzare vecchie edizioni del libro di testo.
	I due appelli di ASD si terranno in contemporanea alla verbalizzazione dei due appelli del corso di Informatica da me insegnato. Tenete quindi d'occhio il sito relativo per le date esatte. Due date probabili sono il 12/07 e il 19/07. Per iscriversi all'esame, mandatemi una email con oggetto "Primo/Secondo Appello ASD: Nome COGNOME" nei giorni 08/07 e 15/07, rispettivamente.
	I due appelli di ASD si terranno nei giorni 12/07 e 19/07 sempre alle 10:00 nel mio ufficio. Per l'iscrizione all'esame seguire le istruzioni che ho dato sopra.
	Per un impegno lavorativo sopraggiunto poco fa, sono costretto a posticipare l'esame al 21/07 (stesso luogo ed orario).
	I due appelli autunnali di ASD si terranno nella stessa data e luogo delle due verbalizzazioni del mio corso "Informatica": fate riferimento al relativo link sul mio sito Web. Per l'iscrizione usate le stesse modalità che per i relativi appelli di Informatica, sostituendo "ASD" ad "Informatica" nell'oggetto della email.