Docente
Lecturer
- Paolo Frasconi
- Dipartimento di Sistemi e Informatica
- Email:
- Ricevimento: Mercoledi 15:00-17:00Office hours: Wednesday 3:00pm-5:00pm
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
- Introdurre le idee fondamentali per l'analisi ed il progetto degli algoritmi.
- Al termine del corso sarete in grado di comprendere ed applicare metodi per analizzare il tempo di esecuzione degli algoritmi, mostrare la loro correttezza, utilizzare soluzioni algoritmiche adeguate per risolvere problemi concreti.
- Introduce the fundamental ideas for analysis and design of algorithms.
- You will be able to understand and apply methods for analizing algorithm running time, prove correctness, and choose correct algorithmic solution to practical problems.
Crediti
Credits
- l'insegnamento vale 6 crediti formativi, formalmente corrispondenti a circa 54 ore di didattica assistita (lezioni ed esercitazioni in classe), e 96 ore di studio individuale.
- The course is worth 6 credits (about 54 hours in class, and 96 hours of individual study).
Prerequisiti
Prerequisites
- I prerequisiti necessari includono una buona comprensione della programmazione procedurale e orientata agli oggetti, le idee fondamentali della matematica discreta (calcolo combinatorio, serie, sommatorie, induzione matematica) e della teoria della probabilità (variabili aleatorie, distribuzioni, valori attesi).
- Normalmente dovete aver frequentato i corsi B003262 - (Fondamenti di informatica), B003271 - (Geometria, algebra lineare e calcolo numerico), e B003426 (Laboratorio di tecnologie dell'informazione) e superato i corrispondenti esami.
- A good understanding of procedural / object-oriented programming, and a solid background in fundamental ideas of discrete mathematics (counting, sequences, summations, mathematical induction) and probability theory (random variables, distributions, expectations), are necessary prerequisites to this course.
- You are expected to have taken B003262 - (Foundations of Computer Science), B003271 - (Geometry, Linear Algebra and Numerical Analysis), and B003426 (Information Technologies Lab) and passed the corresponding exams.
Esame
Exams
- L'esame consiste di un'unica prova orale sull'intero programma del corso.
- Sono previste due sessioni di esami, invernale ed estiva, con 3 e 4 appelli, rispettivamente. In caso di fallimento, non potete tentare nuovamente l'esame in un altro appello nella stessa sessione.
- Potete trovare il calendario su WebTeach, e dovete usarlo per l'iscrizione online alla prova d'esame.
- There is a single oral final exam and it will cover the entire course.
- There are two exam sessions, in winter and summer, with three and four distinct exam dates, respectively. If you fail the exam, you are not allowed to retry on a second date in the same session.
- You can find a calendar on WebTeach. You must use WebTeach to signup for the exam.
Libri di testo
Textbooks
- Libro di testo ufficiale:
[CLRS09] T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein (2009). Introduction to algorithms 3rd ed, MIT Press. Amazon link.
Purtroppo in italiano è solo disponibile la seconda edizione (non consigliata). - Può essere utile la consultazione di:
[MR05] B. N. Miller and D. L. Ranum (2005). Problem Solving with Algorithms and Data Structures Using Python, Franklin, Beedle & Associates Inc. Amazon link.
- The official textbook is:
[CLRS09] T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein (2009). Introduction to algorithms 3rd ed, MIT Press.
Amazon link.
- You may find the following useful:
[MR05] B. N. Miller and D. L. Ranum (2005). Problem Solving with Algorithms and Data Structures Using Python, Franklin, Beedle & Associates Inc. Amazon link.
Programma sintetico
Topics
- Introduzione, analisi, divide et impera. Ordinamento e code con priorità. Dizionari: tabelle hash, alberi binari di ricerca. Programmazione dinamica. Algoritmi elementari sui grafi. Alberi di copertura minimi. Cammini minimi. Esempi di implementazione ed applicazioni degli algoritmi trattati nel corso.
- Introduction, analysis, divide and conquer. Sorting and priority queues. Dictionaries: hashing and binary search trees. Dynamic programming. Elementary graph algorithms. Minimum spanning trees. Shortest paths. Implementation examples and applications of the algorithms covered in the course.
Calendario e materiale didattico
Calendar and handouts
| Data | Argomenti | Letture 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 |
| Date | Topics | Readings 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 |