Paolo Frasconi

B003368: Algoritmi e Strutture Dati (2009/2010)

B003368: Algorithms and Data Structures (2009/2010)

 

C.d.L. Ingegneria Informatica, Università degli Studi di Firenze

B.Sc. Computer Engineering, University of Florence


    Comunicazioni:
  • 01.02.10. Sarò in congedo per motivi di studio presso la K.U. Leuven fino al 31.08.10. Il ricevimento studenti è sospeso fino a tale data ma potete contattarmi per posta elettronica. In alternativa potete parlare con il Prof. Giovanni Soda che ha gentilmente accettato di ricevere gli studenti di questo corso.
  • 30.11.09. A fine anno le strutture didattiche saranno chiuse per risparmio energetico. Di conseguenza la prima prova di esame non potrà svolgersi il 29.12.09. La prima data utile successiva è il 4.01.10. Se avete problemi in tale data, contattatemi per posta elettronica in modo da fissare (compatibilmente con i miei impegni) una data alternativa per il vostro esame nel periodo dal 14.12.09 al 08.01.10.
  • 02.11.09. Il 5 Novembre non ci sarà lezione.
  • 13.10.09. Dal 19 Ottobre, le lezioni del lunedi sono spostate in aula 103 (Morgagni)
  • 30.09.09. Per gli studenti dei previgenti ordinamenti in Ingegneria Informatica: Se lo desiderate, potete sottomettere domanda di variazione del piano di studi e sostenere l'esame di questo corso al posto di Fondamenti di Informatica 2 (disattivato). Tutte queste richieste saranno approvate.
  • Il corso inizia il 21 Settembre 2009
    News:
  • 01.02.10. I am on sabbatical leave at K.U. Leuven until 31.08.10. No office hours until then. However you can email me. Alternatively, please see Prof. Giovanni Soda, who kindly agreed to see students of this course during office hours.
  • 30.11.09. University buildings will be closed for energy savings from 28.12.09 to 03.01.10. Hence, there cannot be exams on 29.12.09. The next possible date is 4.01.10. If this date is problematic with you, please contact me by email to arrange your exam on a date of your choice (compatible with my schedule) from 14.12.09 to 08.01.10.
  • 02.11.09. No class on November 5th.
  • 13.10.09. As of Ottobre 19th, classes will be in room 103 (Morgagni)
  • 30.09.09. To students enrolled in former Computer Engineering curricula: if you wish, you can submit a formal request to take the exam for this course in lieu of Fondamenti di Informatica 2 (not offered anymore). These requests will be all approved.
  • Classes will begin on September 21st, 2009

Docente

Lecturer

Orario delle lezioni

Class schedule

Lunedi 16:00-18:00 Aula 103 (Morgagni)
Giovedi 10:15-13:15 Aula 8 (Morgagni)
Monday 4:00pm-6:00pm Room 103 (Morgagni)
Thursday 10:15am-1:15pm Room 8 (Morgagni)

Obiettivi

Goals

Crediti

Credits

Prerequisiti

Prerequisites

Esame

Exams

Libri di testo

Textbooks

Programma sintetico

Topics

Calendario e materiale didattico

Calendar and handouts

DataArgomentiLetture e materiale*
21/09/2009 Aspetti organizzativi del corso. Introduzione. Analisi degli algoritmi. Invarianti di ciclo. Esempio: Insertion-Sort. CRLS09 Cap. 1, Sez. 2.1, 2.2.
24/09/2009 Analisi di Insertion-sort. Merge-sort. Merge: invariante di ciclo. Analisi di Merge-sort. Notazione asintotica: O, Ω, Θ, o, ω. Definizioni, proprietà, convenzioni nelle espressioni, esempi. CRLS09 Sez. 2.2, 2.3, Cap. 3.
28/09/2009 Soluzione delle ricorrenze: metodo della sostituzione; albero di ricorsione; teorema fondamentale (introduzione). Esempi. Numero di nodi negli alberi k-ari completi. CRLS09 Sez. 4.3, 4.4, 4.5, B.5.3.
01/10/2009 Dimostrazione del teorema fondamentale delle ricorrenze. Algoritmi divide et impera e loro analisi: ricerca binaria, calcolo di potenze intere, calcolo di numeri di Fibonacci, prodotto di matrici, disposizione di un albero binario completo su una griglia 2D. CRLS09 Sez. 4.6, 4.2, appunti della lezione.
05/10/2009 Soluzione degli esercizi: Algoritmo di Euclide per il MCD. Versione iterativa (invariante di ciclo). Versione ricorsiva (analisi). Il problema del massimo sottovettore (MSV). Soluzioni naive in Θ(n3) e Θ(n2), algoritmo divide-et-impera in Θ(n lg n), scansione in Θ(n). CRLS09 Sez. 31.2, 4.1,
J. Bentley (1984). Programming Pearls: Algorithm Design Techniques. Comm. of the ACM 27(9):865-871, Note sul MSV
08/10/2009 Seminario: Breve introduzione a Python. Soluzione degli esercizi: Similarità di documenti (algoritmo naive). Appunti della lezione. http://docs.python.org. DocumentSimilarity: codice Python.
12/10/2009 Quicksort. Correttezza della procedura partition. Analisi: caso peggiore, caso migliore, alternanza di divisioni fortunate e sfortunate. Partizione randomizzata. Analisi del caso medio. CRLS09 Cap 7. App. C
15/10/2009 Modelli di calcolo per l'ordinamento. Alberi di decisione e confine asintotico inferiore per il modello basato su confronti. Ordinamento in tempo lineare: counting-sort, radix-sort. CLRS09 Cap. 8
19/10/2009 Esercitazione. Misurazione sperimentale del tempo di esecuzione di alcuni algoritmi di ordinamento. Sorting.zip: codice Python.
22/10/2009 Hashing. Tabelle ad indirizzamento diretto. Tabelle hash. Chaining. Metodi della divisione e moltiplicazione. Indirizzamento aperto. Doppio hashing. Analisi. CLRS09 Cap. 11.1-11.4 (eccetto 11.3.3)
26/10/2009 Hashing universale. Esempio di costruzione di una classe universale. Hashing perfetto. CLRS09 Cap. 11.3.3, 11.5. Kleimberg and Tardos (2005)Algorithm Design 13.6Note.
29/10/2009 Analisi dell'hashing perfetto. Dizionari in Python, applicazione alla similarità di documenti.
Selezione randomizzata in tempo lineare atteso. Analisi.
CLRS Cap. 11.5, 9.1, 9.2
DocumentSimilarity_2: Python code.
02/11/2009 Alberi binari di ricerca. Rappresentazione. Attraversamenti. Minimo e massimo. Successore e precedessore. Inserimento. Ricerca. Cancellazione. CLRS09 Cap. 12 (eccetto 12.4).
09/11/2009 Alberi binari di ricerca costruiti casualmente: relazione con quicksort randomizzato e valore atteso dell'altezza. Alberi RB. Definizioni. Altezza di un albero RB. CLRS09 Cap. 12.4, 13.1.
L. Devroye (1986) A Note on the Height of Binary Search Trees, J. of the ACM 33(3):489-498, 1986.
12/11/2009 Rotazioni. Inserimento in alberi RB. Estensione di strutture dati: statistiche d'ordine su insiemi dinamici; alberi di intervalli. CLRS09 Cap. 13.2, 13.3, 14.
16/11/2009 Analisi ammortizzata. Cenni al metodo dell'aggregazione ed al metodo del contabile. Applicazione alle tabelle dinamiche.
Code con priorità. Implementazione con heaps binary.
CLRS09 Cap. 17.4, 6.1-6.3,6.5.
Appunti della lezione.
19/11/2009 Programmazione dinamica. Sottosequenza comune più lunga. Distanza di Levenshtein. Seam carving. CLRS09 Cap. 15.3, 15.4, prob. 15-8.
D.S Hirschberg (1975). A linear space algorithm for computing maximal common subsequences. Comm. ACM 18(6):341-343.
S. Avidan and A. Shamir Seam Carving for Content-Aware Image Retargeting SIGGRAPH 2007.
Python code: file diff and seam carving
23/11/2009 Grafi. Definizioni. Rappresentazioni: matrice di incidenza, liste di adiacenza. Visita in ampiezza. Analisi. CLRS09 App. B.4, Cap. 22.1, 22.2.
Python code
26/11/2009 Visita in profondità. Proprietà. Applicazioni: Ordinamento topologico, componenti fortemente connesse.
Algoritmi golosi: Alberi di copertura minimi. Proprietà. Algoritmo di Prim. Analisi.
CLRS09 Cap. 22.3, 22.4, 22.5, 23.1, 23.2 (Prim)
Python code
30/11/2009 Strutture Union-Find. Esempio: componenti connesse dinamiche. Implementazione con liste e foreste. Euristiche: rango e compressione dei cammini. Risultati dell'analisi ammortizzata.
Alberi di copertura minimi: Algoritmo di Kruskal. Analisi.
CLRS09 Cap.21.1, 21.2, 21.3, 23.2 (Kruskal).
Python code
03/12/2009 Cammini minimi da singola sorgente. Proprietà. Algoritmo di Dijkstra. Correttezza e analisi. Algoritmo di Bellman-Ford. Correttezza e analisi. Cammini minimi su DAGs. CLRS09 Ch. 24
Python code
*parte del materiale è protetto da password di accesso. La password viene comunicata esclusivamente agli studenti a lezione.
DateTopicsReadings and handouts*
21/09/2009 Administrivia. Introduction. Analisys of algorithms. Loop invariants. Example: Insertion-Sort. CRLS09 Ch. 1, Sec. 2.1, 2.2.
24/09/2009 Analysis of Insertion-sort. Merge-sort. Merge: loop invariant. Analysis of Merge-sort. Asymptotic notation: O, Ω, Θ, o, ω. Definitions, properties, macro conventions for using in expressions, examples. CRLS09 Sec. 2.2, 2.3, Ch. 3.
28/09/2009 Solving recurrences: substitution method; recursion tree; master theorem (introduction). Examples. Number of nodes in complete k-ary trees. CRLS09 Sec. 4.3, 4.4, 4.5, B.5.3.
01/10/2009 Proof of master theorem. Divide and conquer: binary search, recursive squaring, Fibonacci numbers, matrix multiplication, embedding a complete binary tree on a 2D grid. CRLS09 Sec. 4.6, 4.2. Class notes
05/10/2009 Assignment solution: Euclid's algorithm for GCD. Iterative version (loop invariant). Recursive version (analysis). The maximum subvector problem (MSV). Naive solutions in Θ(n3) e Θ(n2), divide-and-conquer algorithm in Θ(n lg n), scanning algorithm in Θ(n). CRLS09 Sez. 31.2, 4.1,
J. Bentley (1984). Programming Pearls: Algorithm Design Techniques. Comm. of the ACM 27(9):865-871, Notes on MSV (in Italian)
08/10/2009 Seminar: A brief introduction to Python. Assignment solution: Document similarity (naive algorithm). Class notes. http://docs.python.org. DocumentSimilarity: Python code.
12/10/2009 Quicksort. Correctness of the partition algorithm. Analysis: worst case, best case, alternate lucky/unlucky splits. Randomized parition. Average casa analysis. CRLS09 Ch 7. App. C
15/10/2009 Computational models for sorting. Decision tree and lower bound for comparison-based sorting. Sorting in linear time: counting-sort, radix-sort. CLRS09 Ch. 8
19/10/2009 Practice: Measuring execution time of some sorting algorithms. Sorting.zip: Python code.
22/10/2009 Hashing. Direct address tables. Hash tables. Chaining. Division and multiplication method. Open addressing. Double hashing. Analysis. CLRS09 Ch. 11.1-11.4 (except 11.3.3)
26/10/2009 Universal hashing. Example of construction of a universal class. Perfect hashing. CLRS09 Ch. 11.3.3, 11.5. Kleimberg and Tardos (2005)Algorithm Design 13.6Notes.
29/10/2009 Analysis of perfect hashing. Python dictionaries, application to document similarity.
Randomized selection in expected linear time. Analysis.
CLRS09 Ch. 11.5, 9.1, 9.2
DocumentSimilarity_2: Python code.
02/11/2009 Binary search trees. Representation. Traversal. Minimum and maximum. Successor and precedessor. Insertion. Search. Deletion. CLRS09 Ch. 12. (except 12.4)
09/11/2009 Randomly built binary search trees: relationships to randomized quicksort and expected height. RB Trees. Definitions. Height of a RB-tree. CLRS09 Ch. 12.4, 13.1.
L. Devroye (1986) A Note on the Height of Binary Search Trees, J. of the ACM 33(3):489-498, 1986.
12/11/2009 Rotations. Insertion in RB-trees. Augmenting data structures: Dynamic order statistics; interval trees. CLRS09 Ch. 13.2, 13.3, 14.
16/11/2009 Amortized analysis. Basic ideas for aggregation method and accounting method. Applications to dynamic tables.
Priority queues. Implementation with binary heaps.
CLRS09 Ch. 17.4, 6.1-6.3,6.5.
Class notes.
19/11/2009 Dynamic programming. Longest common subsequence. Levenshtein (edit) distance. Seam carving. CLRS09 Ch. 15.3, 15.4, prob. 15-8.
D.S Hirschberg (1975). A linear space algorithm for computing maximal common subsequences. Comm. ACM 18(6):341-343.
S. Avidan and A. Shamir Seam Carving for Content-Aware Image Retargeting SIGGRAPH 2007.
Python code: file diff and seam carving
23/11/2009 Graphs. Definitions. Representations: incidence matrix, adjacency lists. Breadth-first search. Analysis. CLRS09 App. B.4, Ch. 22.1, 22.2.
Python code
26/11/2009 Depth-first Search. Properties. Applications: Topological sort, strongly connected components.
Greedy algorithms: Minimum spanning trees. Properties. Algorithm of Prim. Analysis.
CLRS09 Ch. 22.3, 22.4, 22.5, 23.1, 23.2 (Prim)
Python code
30/11/2009 Union-Find data structures. Motivating example: dynamic connected components. Implementation with lists and forests. Heuristics: rank and path compression. Results of amortized analysis.
Minimum spanning trees: Algorithm of Kruskal. Analysis
CLRS09 Ch.21.1, 21.2, 21.3, 23.2 (Kruskal).
Python code
03/12/2009 Single source shortest paths. Properties. Dijkstra's algorithm. Correctness and analysis. The Bellman-Ford algorithm. Correctness and analysis. Shortest paths on DAGs. CLRS09 Ch. 24
Python code
*some handouts are password protected. The password is only revealed to students in class.