Algorithms and Data Structures (2004/2005)

Course Not running, not visible

Teaching is organised as follows:
Unit Credits Academic sector Period Academic staff
Teoria 8 1° Q - 2° anno e successivi, 2° Q Roberto Segala
Laboratorio 2 1° Q - 2° anno e successivi, 2° Q Roberto Segala

Learning outcomes

Modulo: Laboratorio
-------
Nel corso vengono raffinate le conoscenze dello studente circa la pratica della programmazione a oggetti, soprattutto nell'implementazione di algoritmi e strutture dati avanzate. Le lezioni sono svolte in linguaggio Java di cui si assume una conoscenza di base.


Modulo: Teoria
-------
Nel corso vengono esaminati i concetti di base per la formulazione di soluzioni algoritmiche a problemi concreti. Vengono studiate soluzioni a problemi formulati in termini di strutture matematiche astratte (liste, code, grafi, ...) e vengono descritte metodologie per identificare i problemi astratti che più si addicono allo studio di un problema concreto. Gli algoritmi vengono valutati e confrontati in base alla quantità di risorse che richiedono. Il corso si concentra inoltre sul ruolo che ha lo studio delle strutture di dati nella formulazione e valutazione di nuovi algoritmi.

Syllabus

Modulo: Laboratorio
-------
Il corso di laboratorio viene svolto in 24 ore di esercitazione in laboratorio suddivise in 8 lezioni da 3 ore ciascuna. Si ricorda che il corso vale 2 CFU, per cui sono previste ulteriori 25 ore di lavoro individuale da svolgersi presso i laboratori didattici.

Lezione 1: Uso del meccanismo dell'Interfaccia. Esempio di applicazione con l'implementazione dell'ADT Lista, Coda e Pila.

Lezione 2: Uso dell'interfaccia Comparable. Implementazione degli algoritmi di ordinamento per inserimento (InsertionSort) e per passo calante (ShellSort).

Lezione 3: Tecniche di confronto di implementazioni. Confronto tra due implementazioni di algoritmi di ordinamento: QuickSort e MergeSort.

Lezione 4: Implementazioni dell'ADT HashTable.

Lezione 5: Implementazione di un algoritmo di programmazione dinamica: ricerca massima sottosequenza comune (MaxSSC).

Lezione 6: Implementazioni dell'ADT Albero e Albero di ricerca binario. Uso dell'interfaccia Iterator. Implementazioni metodi di visita.

Lezione 7: Implementazione di un algoritmo greedy: algoritmo di Kruskal.


Modulo: Teoria
-------
l corso viene svolto in 64 ore di lezione frontale, di cui 32 ore nel primo quadrimestre e 32 ore nel secondo quadrimestre. Nelle 64 ore di lezione sono comprese 20 ore di esercitazione durante le quali gli studenti devono risolvere problemi specifici sotto la guida del docente.

Complessità: complessità degli algoritmi, notazione asintotica, metodi di risoluzione delle equazioni di ricorrenza, analisi ammortizzata.


Ordinamento e Selezione: insertion sort, merge sort, heap sort, quick sort, quick sort probabilistico. Studio della complessità degli algoritmi di ordinamento, limite inferiore dell'ordinamento per confronti. Algoritmi lineari, counting sort, radix sort, bucket sort. Algoritmi di selezione, minimo, massimo, selezione in tempo medio lineare, selezione in tempo pessimo lineare.


Strutture dati: Code, pile, liste, heap, alberi binari di ricerca, alberi RB, heap binomiali, insiemi disgiunti, tecniche di estensione di una struttura dati.


Grafi: Definizione e rappresentazione di un grafo, visita in ampiezza, visita in profondità, ordinamento topologico, componenti connesse, alberi di copertura di costo minimo (Prim e Kruskal), cammini minimi a sorgente singola (Dijkstra e Bellman-Ford) e multipla (Floyd-Warshall e Johnson), flusso massimo (Ford-Fulkerson, Karp), matching massimale su grafo bipartito.

Lezione 1:Introduzione al corso, Elementi di complessità.
Riferimenti: [CLR] Capitolo 1. Si consiglia di ripassare il materiale dei capitoli 3 e 5.

Lezione 2:Complessità degli algoritmi, Notazione asintotica O(f), Omega(f), e Theta(f).
Riferimenti: [CLR] Capitolo 2.

Lezione 3: Algoritmi ricorsivi, Risoluzione di equazioni di ricorrenza (metodo iterativo, metodo di sostituzione, teorema principale).
Riferimenti: [CLR] Capitolo 4 Sezioni 1-3.

Lezione 4: Algoritmi di ordinamento, &Insertion sort, merge sort, Studio della complessità, Stabilità e ordinamento in loco.
Riferimenti: [CLR] Capitolo 1.

Lezione 5: Algoritmi di ordinamento: heap sort.
Riferimenti: [CLR] Capitolo 7.

Lezione 6: Algoritmi di ordinamento: quick sort, quick sort probabilistico, Limite inferiore alla complessità di ordinamento per confronti.
Riferimenti: [CLR] Capitolo 8 Sezioni 1-3.

Lezione 7:Algoritmi di ordinamento lineari: counting sort, radix sort, bucket sort.
Riferimenti: [CLR] Capitolo 9.

Lezione 8:Algoritmi di Selezione. Tempi medio e peggiore lineari.
Riferimenti: [CLR] Capitolo 10.

Lezione 9: Strutture dati elementari. Stack, code, liste,
Alberi binari di ricerca
Riferimenti: [CLR] Capitoli 11 e 13.

Lezione 10:RB-alberi.
Riferimenti: [CLR] Capitolo 14.

Lezione 11: Estensione di una struttura dati. Alberi di intervalli.
Riferimenti: [CLR] Capitolo 15.

Lezione 12:Heap binomiali.
Riferimenti: [CLR] Capitolo 20.

Lezione 13:Strutture per insiemi disgiunti.
Riferimenti: [CLR] Capitolo 22.

Lezione 14:Programmazione dinamica.
Riferimenti: [CLR] Capitolo 16.

Lezione 15:Algoritmi greedy.
Riferimenti: [CLR] Capitolo 17 Sezioni 1-3.

Lezione 16:Grafi: definizione e rappresentazione.
Riferimenti: [CLR] Capitolo 23 Sezione 1.

Lezione 17:Visita di grafi. BFS, DFS.
Riferimenti: [CLR] Capitolo 23 Sezioni 2-3.

Lezione 18: Ordinamento topologico. Componenti connesse.
Riferimenti: [CLR] Capitolo 23 Sezioni 4-5.

Lezione 19:Alberi di copertura di costo minimo. Algoritmi di Kruskal e Prim.
Riferimenti: [CLR] Capitolo 24.

Lezione 20:Cammini minimi. Algoritmi di Dijkstra e Bellman-Ford per sorgente singola.
Riferimenti: [CLR] Capitolo 25.

Lezione 21:Cammini minimi. Algoritmi di Floyd-Warshall e Johnson per sorgenti multiple.
Riferimenti: [CLR] Capitolo 26.

Lezione 22:Flusso massimo. Algoritmo di Ford-Fulkerson. Matching massimale su grafo bipartito.
Riferimenti: [CLR] Capitolo 27 Sezioni 1-3.

Assessment methods and criteria

Modulo: Laboratorio
-------
L'esame di algoritmi e strutture dati è unico per entrambe i moduli di teoria e laboratorio. L'esercitazione scritta prevista per l'esame prevede un esercizio che verifica la capacità di formulare un algoritmo nel linguaggio Java. Si vedano le modalità di esame del modulo di teoria per le condizioni di superamento dell'esercitazione scritta e per le modalità di svolgimento del successivo esame orale.


Modulo: Teoria
-------
L'esame di algoritmi e strutture dati è orale. Per l'ammissione all'esame lo studente deve superare una esercitazione scritta di 3 ore che consiste in tre esercizi sulla parte di teoria e un esercizio sulla parte di laboratorio. Gli esercizi sulla parte di teoria sono di difficoltà crescente e cercano di valutare sia le conoscenze acquisite che le capacità di ragionamento nell'ambito della materia. L'esercizio sulla parte di laboratorio verifica la capacità di formulare un algoritmo nel linguaggio Java. L'esercitazione scritta si intende superata se lo studente ottiene una votazione di almeno 18/30 considerando che ogni esercizio vale 1/4 del punteggio totale.

All'esercitazione scritta lo studente può portare un foglio formato A4 scritto su entrambe le facciate a penna di proprio pugno. Su ogni facciata il foglio deve riportare nome, cognome, e numero di matricola. Non sono imposti limiti ai contenuti del foglio A4.

Alla prova orale lo studente può decidere di verbalizzare il voto dell'esercitazione scritta o di essere riesaminato mediante colloquio. In tal caso il voto finale dell'esame sarà basato puramente sul colloquio senza tenere in alcun conto l'esito dell'esercitazione scritta.

Reference books
Author Title Publisher Year ISBN Note
T. Cormen, C. Leiserson, R. Rivest, C. Stein Introduzione agli Algoritmi e Strutture Dati (Edizione 2) McGraw-Hill 2005 88-386-6251-7

Studying