Ingegneria degli algoritmi

Paolo Ferragina      Tel. 0502212764

In questo corso studieremo, progetteremo e analizzeremo (con modelli teorici e attraverso risultati sperimentali) soluzioni algoritmiche e strutture dati avanzate per la risoluzione efficiente di problemi combinatori che coinvolgono vari tipi di dato? quali interi, stringhe, punti (geometrici), alberi, grafi. Il progetto interesserà alcuni modelli di calcolo? RAM, 2-level memory, cache-oblivious, streaming? al fine di ottenere soluzioni algoritmiche le cui valutazioni teoriche ben riflettono le loro prestazioni reali, poiché tengono conto delle caratteristiche architetturali e della gerarchia di memoria dei moderni PC. Ogni lezione seguirà un approccio problem-driven che inizia considerando un problema reale, lo astrae in modo combinatorio, e poi procede al progetto e analisi di soluzioni algoritmiche tese a minimizzare l'uso di alcune risorse computazionali quali: tempo, spazio, communicazione, I/O, etc. Alcune soluzioni viste in classe saranno discusse anche a livello sperimentale al fine di introdurre degli strumenti appropriati per l' ingegnerizzazione e il tuning del codice.

---

Objectives
In this course we will study, design and analyze (theoretically and experimentally) advanced algorithms and data structures for the efficient solution of combinatorial problems involving all basic data types, such as integers, strings, (geometric) points, trees and graphs. These algorithmic tools will be designed and analyzed in several models of computation— such as RAM, 2-level memory, cache-oblivious, streaming— in order to take into account the architectural features and the memory hierarchy of modern PCs.
Every lecture will follow a problem-driven approach that starts from a real software-design problem, abstracts it in a combinatorial way (suitable for an algorithmic investigation), and then introduces algorithmic solutions aimed at minimizing the use of some computational resources like time, space, communication, I/O, etc. Some of these solutions will be discussed at an experimental level, in order to introduce proper engineering and tuning tools for algorithmic development.

In this course we will study, design and analyze (theoretically and experimentally) advanced algorithms and data structures for the efficient solution of combinatorial problems involving all basic data types, such as integers, strings, (geometric) points, trees and graphs. These algorithmic tools will be designed and analyzed in several models of computation? such as RAM, 2-level memory, cache-oblivious, streaming? in order to take into account the architectural features and the memory hierarchy of modern PCs. Every lecture will follow a problem-driven approach that starts from a real software-design problem, abstracts it in a combinatorial way (suitable for an algorithmic investigation), and then introduces algorithmic solutions aimed at minimizing the use of some computational resources like time, space, communication, I/O, etc. Some of these solutions will be discussed at an experimental level, in order to introduce proper engineering and tuning tools for algorithmic development.

1. RAM model a. Data compression b. Data processing: randomized, adaptive, self-adjusting c. Data indexing and searching: strings, geometric points, trees and graphs
2. 2-level memory model a. Definition and properties b. Data sorting and permuting c. Data indexing and searching: strings and multi-dimensional data d. Data sketching: bloom filters and count-min sketch
3. Cache-oblivious model a. Definition and properties b. Matrix multiplication c. VEB layout d. Tree mapping

---

Syllabus

1. RAM model Data compression Data processing: randomized, adaptive, self-adjusting. Data indexing and searching: strings, geometric points, trees and graphs
2. 2-level memory model Definition and properties Data sorting and permuting Data indexing and searching: strings and multi-dimensional data Data sketching: bloom filters and count-min sketch
3. Cache-oblivious model Definition and properties Matrix multiplication VEB layout Tree mapping