Strumenti Utente

Strumenti Sito


magistraleinformaticanetworking:ae:start

Questa è una vecchia versione del documento!


Algorithm Engineering

Thanks to P. Sanders Teacher: Paolo Ferragina

CFU: 6.

Language: English.

Degree: Master degree in Computer Science and Networking, University of Pisa and Scuola Normale Superiore “S. Anna”.


Goals

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, energy, etc. Some of these solutions will be discussed at an experimental level, in order to introduce proper engineering and tuning tools for algorithmic development.

Background

If you wish to refresh your mind on Algorithms and Data Structures, I suggest you to follow the Video Lectures by Erik Demaine and Charles Leiserson, specifically Lectures 1-5, 7 and 10. There it is missing the part on basic graph problems (representation, DFS, BFS, topological sort) which you may browse in any book, such as Introduction to Algorithms by Cormen-Leiserson-Rivest-Stein, third edition.

Teaching material

magistraleinformaticanetworking/ae/start.1379922744.txt.gz · Ultima modifica: 23/09/2013 alle 07:52 (11 anni fa) da Paolo Ferragina