Ingegneria degli Algoritmi / Algorithm Engineering
- L'esame di mercoledì 18 settembre è posticipato a giovedì 19 settembre, ore 9:30, presso il mio studio.
- Date esami: martedì 11 giugno, mercoledì 10 luglio, mercoledì 18 settembre. Tutti gli appelli si svolgono alle ore 9:00 in Aula Seminari.
- Articoli per tesine:
- Triangle counting 1: Reductions in streaming algorithms with an application to counting triangles in graphs, Bar-Yossef, Kumar & Sivakumar, ACM-SIAM Symposium on Discrete Algorithms, 2002 (Cammarano & Mile)
- Triangle counting 2: On the streaming complexity of computing local clustering coefficients, Kutzkov & Pagh, ACM Conference on Web Search and Data Mining, 2013 (Mauro)
- Frequent items 1: An integrated efficient solution for computing frequent and top-k elements in data streams, Metwally, Agrawal & El Abbadi, ACM Transactions on Database Systems, 2006 (Carnevale & Papandrea)
- Frequent items 2: Mining frequent items in a stream using flexible windows, Calders, Dexters & Goethals, ACM Conference on Knowledge Discovery and Data Mining, 2010 (Iovino)
- Count-min sketch: An improved data stream summary: the count-min sketch and its applications, Journal of Algorithms, 2005 (Ciciarelli)
- Repeated elements: Finding repeated elements, Misra & Gries, Science of Computer Programming, 1982 (Colazzo & Rauso)
- Sorting & selection: Selection and sorting with limited storage, Theoretical Computer Science, 1980 (Bronzini)
|| aula Alfa
|| aula Alfa
Descrizione del corso
The course will cover fundamental techniques for bridging algorithmic theory and programming practice: it will offer a general introduction to the area of Algorithm Engineering and to the major techniques and research topics in this area.
The aim of algorithm engineering is to conjugate the design and theoretical analysis of efficient algorithms and data structures with their actual implementation and experimental analysis on modern computer platforms. The lectures will follow an experimental and problem-driven approach. The goal for the class is to be broad rather than deep: our plan is to touch upon a variety of areas and techniques. This is a tentative list of questions that are likely be covered in the class:
- The running times obtained in practice by scanning a moderately large matrix by row or by column may be very different: what is the reason? Is the assumption that memory access times are constant realistic?
- How would you sort 1TB of data? How would you measure the performances of algorithms in applications that need to process massive data sets stored in secondary memories?
- Do memory allocation and free operations really require constant time? How do real memory allocators work?
- How can we maintain statistics related to the traffic routed by a backbone server? The observed data are a continuous and possibly infinite stream that cannot be stored explicitly. What can be computed without even storing the input?
- For several decades, most classes of applications have enjoyed free and regular performance gains thanks to faster clock speeds. In multicore platforms, the free lunch is over. How can algorithms take advantage of multiple cores? Which are the main algorithmic and programming challenges in the multicore era?
In the course we will introduce computational models that, differently from the standard RAM model considered in undergraduate courses, take into account architectural aspects of modern computer platforms such as the presence of memory hierarchies and multiple cores. We will show how to design efficient algorithms and data structures in such models and how to analyze them both by theoretical and by experimental means. Along the way, we will introduce advanced tools for engineering and tuning the performance of algorithmic code.
Diario delle lezioni
Trovate a questo link
il diario delle lezioni dettagliato, oltre a dispense, slides, articoli e riferimenti bibliografici.
Diario delle lezioni A.A. 2011-2012
- Familiarity with problems and techniques in algorithm engineering
- Knowledge of advanced computational models, such as external memory, data streaming, cache-oblivious, multi-core.
- Ability to design algorithms and data structures and to write efficient code taking into account architectural features of modern computer platforms.
- Performance analysis skills using both mathematical and experimental tools.
- Ability to study advanced research topics in algorithmics
Libri e materiale didattico
- J. Bentley. Programming pearls, 2/ed, Addison-Wesley, 2000. Book web site.
- R. Bryant, D. O'Hallaron: Computer Systems: A Programmer's Perspective, Prentice Hall, 2003.
- C. Demetrescu, I. Finocchi, G. F. Italiano. Algoritmi e strutture dati, 2/ed, McGraw-Hill, 2008.
- K. Mehlhorn, P. Sanders. Algorithms and data structures: The basic toolbox, Springer, 2009. Book web site.
- M. Herlihy, N. Shavit. The Art of Multiprocessor Programming, Morgan Kaufmann, 2008.
- C. Demetrescu, I. Finocchi. Algorithms for data streams. In Handbook of Applied Algorithms, John Wiley and Sons, 2008
- Research papers that will be posted on-line during the course
L'esame consiste di due prove:
- un "orale-scritto", ovvero uno scritto con domande aperte tipiche da esame orale, tese a verificare la conoscenza e la comprensione di base della materia (e.g., descrizione ed analisi di algoritmi e strutture dati presentati durante il corso);
- la presentazione di una tesina concordata con il docente durante il corso. Le tesine possono essere svolte a coppie e verranno presentate dagli studenti in aula durante le ultime due settimane di corso.
Nella settimana di interruzione della didattica è prevista una prova intermedia sugli argomenti affrontati nella prima parte del corso (nell'A.A. 2012-2013: algoritmi per data stream).