Module page
Algorithms and data structures
| academic year: | 2013/2014 |
| instructor: | Alessandro Panconesi |
| degree course: | Mathematics - DM 270/04 (triennale), III year |
| type of training activity: | affine e integrativa |
| credits: | 6 (48 class hours) |
| scientific sector: | INF/01 Informatica |
| teaching language: | italiano |
| period: | II sem (03/03/2014 - 13/06/2014) |
Lecture meeting time and location
Presence: highly recommended
Module aims:
Nowadays it is difficult to underestimate the importance of algorithms. From WallStreet to the Internet, through a myriad of artifacts, for better or for worse, algorithms govern fundamental aspects of our daily lives. The purpose of this course is to illustrate the basic concept of efficient algorithm and to develop the basics of the sophisticated mathematical theory that makes it possible their design and implementation.
Module subject: DFS and BFS. Greedy algorithms: Dijkstra's algorithm, minimum spanning trees Data structures: heaps, union-find Divide and conquer Dynamic programming: edit distance, shortest paths (Bellman-Ford) Max flow: Ford-Fulkerson, Preflow-push (push relabel), max flow - min cut theorem and its applications NP-completeness (sketch) Probabilistic algorithms: min cut, quicksort
Suggested readings:
- Kleinberg-Tardos, Algorithm design-- Pearson international
- There are several books that cover the same material such as Cormen, Leiserson, Rivest: "Introduction to Algorithms" but Kleinberg-Tardos seems to me the best at the moment.
Type of course: standard
Prerequisites:
Informatica Generale
Knowledge and understanding:
implementare un qualunque algoritmo progettato, nonché le strutture dati relative, in un linguaggio di programmazione strutturata, quale ad esempio il C++, e di mandarlo in esecuzione sotto diversi sistemi operativi.
Skills and attributes:
implement any projected algorithm and the relative data structures in a structured programming language, like C. They will be, also, able to run any program under different operating systems.
Personal study: the percentage of personal study required by this course is the 65% of the total.