Docente
Lecturer
- Paolo Frasconi
- Dipartimento di Sistemi e Informatica
- Email:
- Ricevimento: Giovedi 15:00-17:00Office hours: Thursday 3:00pm-5:00pm
Orario delle lezioni
Class schedule
| Lunedi | 16:00-18:00 | Aula 103 (Morgagni) |
| Martedi | 10:15-13:15 | Aula 008 (Morgagni) |
| Monday | 4:00pm-6:00pm | Room 103 (Morgagni) |
| Tuesday | 10:15am-1:15pm | Room 008 (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. In caso di fallimento, non potete tentare nuovamente l'esame in un altro appello nella stessa sessione.
- Per il calendario, consultate il Servizio di Prenotazione Esami di Ateneo
- A partire da quest'anno la verbalizzazione è elettronica e pertanto è obbligatoria la registrazione online usando questo link.
- There is a single oral final exam and it will cover the entire course.
- There are two exam sessions, in winter and summer. If you fail the exam, you are not allowed to retry on a second date in the same session.
- To see the calendar, please visit University Exam Booking System
- Exams will be recorded electronically starting from this year. Therefore you must enroll online using this link.
Libri di testo
Textbooks
- Libro di testo ufficiale:
[CLRS09] T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein (2009). Introduzione agli algoritmi, 3/ed, McGraw-Hill (MIT Press). Amazon link. - 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.
Software
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* |
| 11/10/2010 | Aspetti organizzativi del corso. Introduzione. Analisi degli algoritmi. Invarianti di ciclo. Esempio: Insertion-Sort. | CRLS09 Cap. 1, Sez. 2.1, 2.2. insertion_sort.py |
|---|---|---|
| 12/10/2010 | Analisi di Insertion-Sort. Notazione asintotica. Esempio di divide et impera: Merge-Sort. Correttezza di Merge. Introduzione alle ricorrenze. | CRLS09 2.3, Cap. 3. merge_sort.py |
| 18/10/2010 | 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. |
| 19/10/2010 | 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. |
| 25/10/2010 | Analisi probabilistica. Il problema delle assunzioni. Breve introduzione alla probabilità, variabili aleatorie discrete, valore atteso. | CRLS09 5.1, App. C |
| 26/10/2010 | Analisi del problema delle assunzioni. Quicksort. Correttezza della procedura partition. Analisi: caso peggiore, caso migliore, alternanza di divisioni fortunate e sfortunate. Partizione randomizzata. Analisi del caso medio. 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. | CLRS09 5.2, 7, 8.1, 8.2 |
| 2/11/2010 | Radix-sort. Esercitazione: Misura del tempo di esecuzione in python. | CRLS09 8.3. Python code |
| 9/11/2010 | 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) |
| 15/11/2010 | Hashing universale. Costruzione di una classe universale di funzioni hash. Hash perfetto. | CLRS09 Ch. 11.3.3, 11.5. Kleimberg and Tardos (2005)Algorithm Design 13.6Notes. |
| 16/11/2010 | Alberi binari di ricerca. Rappresentazione. Visite. Minimo, massimo, successore, predecessore. Ricerca, inserimento, cancellazione. Selezione randomizzata in tempo lineare atteso. Analisi. | CLRS09 Ch. 12. (eccetto 12.4), 9.1, 9.2 |
| 22/11/2010 | Alberi binari di ricerca costruiti casualmente: relazione con quicksort randomizzato e valore atteso dell'altezza. | CLRS09 Cap. 12.4. L. Devroye (1986) A Note on the Height of Binary Search Trees, J. of the ACM 33(3):489-498, 1986. |
| 29/11/2010 | Esercitazione: Soluzione al problema della similarità tra documenti con dizionari (C++ and Python). |
DocumentSimilarity.tgz: C++ and Python code. |
| 6/12/2010 | Alberi RB. Definizioni. Altezza di un albero RB. Rotazioni. Inserimento negli alberi RB. Alber AVL (definizione e altezza). Treaps. | CLRS09 Ch. 13.2, 13.3, 14. Seidel and Aragon (1996) Randomized search trees. |
| 7/12/2010 | Strutture dati aumentate. Statistiche d'ordine con alberi RB (OS-Select, OS-Rank). Alberi di intervalli. | CLRS09 Ch. 14. |
| 13/12/2010 | Programmazione dinamica. Sottosequenza comune più lunga. Distanza di Levenshtein (edit distance) Algoritmo di Needleman-Wunsch algorithm per allinemento di coppie di sequenze. Sottosequenza comune più lunga in spazio lineare. | CLRS09 Ch. 15.3, 15.4. D.S Hirschberg (1975). A linear space algorithm for computing maximal common subsequences. Comm. ACM 18(6):341-343. |
| 14/12/2010 |
Esercitazione. Seam carving: Teoria e implementazione Python. File diff. Analisi ammortizzata. Tabelle dinamiche. Metodo dell'aggregazione. Metodo del contabile. |
S. Avidan and A. Shamir
Seam Carving for Content-Aware Image Retargeting
SIGGRAPH 2007. CLRS09 Ch. 17.4. Python code: LCS, File diff, seam carving |
| 20/12/2010 | Grafi. Definizioni. Reppresentazioni: matrice di incidenza, liste di adiacenza. Visita in ampiezza. Analisi. Visita in profondità. Proprietà. Applicazione: Ordinamento topologico. | CLRS09 App. B.4, Ch. 22.1, 22.2. |
| 21/12/2010 |
Componenti fortemente connesse. Algoritmi golosi: Alberi di copertura minimi. Propriertà. Algoritmo di Prim. Analisi. Code con priorità, implementazione con heap binario. |
CLRS09 Ch. 23.1, 23.2 (Prim), 6.1-6.3,6.5 Python code (BFS, DFS, Priority Queues, Prim) |
| 10/1/2011 |
Code a minima priorità con heaps binari: Dettagli implementativi.
Alberi di copertura minimi: Algoritmo di Kruskal.
Strutture Union-Find.
Implementazione con liste e foreste. Euristiche: rango e compressione dei cammini.
Analisi ammortizzata (risultati). Analisi di Kruskal. Introduzione ai cammini minimi da singola sorgente. |
CLRS09 Ch.21.1, 21.2, 21.3, 23.2 (Kruskal). Python code |
| 11/1/2011 | Algoritmo di Dijkstra's. Correttezza e analisi. Algoritmi di Bellman-Ford. Correttezza e analisi. Cammini minimi nei DAGs. | CLRS09 Ch. 24 Python code |
| Date | Topics | Readings and handouts* |
| 11/10/2010 | Administrivia. Introduction. Analisys of algorithms. Loop invariants. Example: Insertion-Sort. | CRLS09 Ch. 1, Sec. 2.1, 2.2. |
|---|---|---|
| 12/10/2010 | Analysis of Insertion-Sort. Asimptotic notation. Divide and Conquer example: Merge-Sort. Correcness of Merge. Introduction to recurrences. | CRLS09 2.3, Ch. 3. merge_sort.py |
| 18/10/2010 | 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. |
| 19/10/2010 | 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 |
| 25/10/2010 | Probabilistic analysis. The hiring problem. Brief review of probability, discrete random variables, expected value. | CRLS09 5.1, App. C |
| 26/10/2010 | Analysis of the hiring problem. Quicksort. Correctness of the partition algorithm. Analysis: worst case, best case, alternate lucky/unlucky splits. Randomized parition. Average case analysis. Computational models for sorting. Decision tree and lower bound for comparison-based sorting. Sorting in linear time: counting-sort. | CLRS09 5.2, 7, 8.1, 8.2 |
| 2/11/2010 | Radix-sort. Practice: measuring running time in python. | CRLS09 8.3. Python code |
| 9/11/2010 | 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) |
| 15/11/2010 | 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. |
| 16/11/2010 | Binary search trees. Representation. Traversal. Minimum and maximum. Successor and precedessor. Insertion. Search. Deletion. Randomized selection in expected linear time. Analysis. | CLRS09 Ch. 12. (except 12.4), 9.1, 9.2 |
| 22/11/2010 | Randomly built binary search trees: relationship to randomized quicksort. Expected height. | CLRS09 Cap. 12.4. L. Devroye (1986) A Note on the Height of Binary Search Trees, J. of the ACM 33(3):489-498, 1986. |
| 29/11/2010 | Exercise: Solving the document similarity problem with dictionaries (C++ and Python). |
DocumentSimilarity.tgz: C++ and Python code. |
| 6/12/2010 | RB Trees. Definitions. Height of a RB-tree. Rotations. Insertion in RB-trees. AVL-trees (definition and height). Treaps. | CLRS09 Ch. 13.2, 13.3, 14. Seidel and Aragon (1996) Randomized search trees. |
| 7/12/2010 | Augmenting data structures: Dynamic order statistics on RB trees (OS-Select, OS-Rank). Interval trees. | CLRS09 Ch. 14. |
| 13/12/2010 | Dynamic programming. Longest common subsequence. Levenshtein (edit) distance. Needleman-Wunsch algorithm for pairwise sequence alignment. Linear space longest-common subsequence. | CLRS09 Ch. 15.3, 15.4. D.S Hirschberg (1975). A linear space algorithm for computing maximal common subsequences. Comm. ACM 18(6):341-343. |
| 14/12/2010 |
Practice. Seam carving: Theory and Python implementation. File diff. Amortized analysis. Dynamic tables. Aggregate method. Accounting method. |
S. Avidan and A. Shamir
Seam Carving for Content-Aware Image Retargeting
SIGGRAPH 2007. CLRS09 Ch. 17.4. Python code: LCS, File diff, seam carving |
| 20/12/2010 | Graphs. Definitions. Representations: incidence matrix, adjacency lists. Breadth-first search. Analysis. Depth-first Search. Properties. Applications: Topological sort. | CLRS09 App. B.4, Ch. 22.1, 22.2. |
| 21/12/2010 |
Strongly connected components. Greedy algorithms: Minimum spanning trees. Properties. Algorithm of Prim. Analysis. Heap implementation of priority queues. |
CLRS09 Ch. 23.1, 23.2 (Prim), 6.1-6.3,6.5 Python code (BFS, DFS, Priority Queues, Prim) |
| 10/1/2011 |
Min-priority queues with binary heaps: Implementation details.
Minimum spanning trees: Algorithm of Kruskal.
Union-Find data structures.
Implementation with lists and forests. Heuristics: rank and path compression.
Results of amortized analysis. Analysis of Kruskal. Introduction to single source shortest paths. |
CLRS09 Ch.21.1, 21.2, 21.3, 23.2 (Kruskal). Python code |
| 11/1/2011 | Dijkstra's algorithm. Correctness and analysis. The Bellman-Ford algorithm. Correctness and analysis. Shortest paths on DAGs. | CLRS09 Ch. 24 Python code |