Ingegneria degli Algoritmi / Algorithm Engineering

Corso di Laurea Magistrale in Informatica

A.A. 2012-2013, secondo semestre

Docente: Irene Finocchi

Ricevimento: per appuntamento

Avvisi

  • 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)

Orari

giorno ora luogo
lunedì 12.00-13.30 aula Alfa
mercoledì 10.15-11.45 aula Alfa

Descrizione del corso english flag

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

Obiettivi formativi english flag

  • 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

Modalità d'esame

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).

Edit | Attach | Watch | Print version | History: r52 < r51 < r50 < r49 < r48 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r52 - 2013-09-16 - IreneFinocchi






 
Questo sito usa cookies, usandolo ne accettate la presenza. (CookiePolicy)
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2017 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback