Docente

Prof. Alberto Policriti

Indirizzo e-mail

alberto.policriti@uniud.it

Indirizzo Pagina Web Personale

http://www.dimi.uniud.it/policriti

Crediti

6 CFU

Finalità e obbiettivi formativi

Il principale obiettivo del corso è quello di approfondire alcuni degli argomenti studiati nel corso di Algoritmi e Strutture Dati, introducendo problematiche e strumenti relativi ad alcuni settori in cui la teoria degli algoritmi gioca oggi un ruolo fondamentale. I temi scelti a questo scopo sono gli algoritmi su stringhe ed alberi e le relative strutture dati, gli algoritmi paralleli e gli algoritmi randomizzati. Si accennerà infine alla algoritmica basata su una rappresentazione simbolica dei dati. La vastità dei campi permetterà, soprattuto per i temi studiati nella seconda e terza parte, solo una introduzione ma la centralità, la pervasività e l’eleganza delle idee presentate ne giustifica e motiva il trattamento.

Il corso si dividerà quindi in tre parti: nella prima parte si studieranno problematiche relative al disegno ed utilizzo di algoritmi di string matching e alla analisi della complessità degli algoritmi. Nella seconda parte si studieranno i principali modelli e architetture parallele, insieme alle tecniche fondamentali per l'analisi ed il disegno di algoritmi paralleli. Nella terza parte si studieranno i fondamenti della teoria degli algoritmi randomizzati rivisitando algoritmi noti nella loro versione randomizzata.

Si prevede, durante la parte finale del corso, un'attività seminariale e di approfondimento e introduzione alla ricerca.

Programma

1. Prima parte: Introduzione. Il problema dello string matching esatto: algoritmi di Knuth-Morris e Pratt, Rabin e Karp, Boyer e Moore. Suffix trees e applicazioni, algoritmo di Ukkonen e McCreight, algoritmo di Harel e Tarjan per il calcolo del lowest common ancestor. Algoritmo di Aho e Coarsik. Il problema dello string matching approssimato: algoritmo di Sellers, algoritmo di Landau e Vishkin, algoritmo di Chang e Lawler.
2. Seconda parte: Sorting networks: introduzione, running time, bitonic e merging algorithms. Modelli e algoritmi per computers paralleli: il modello PRAM, pointer jumping, teorema di Brent, esempi. Fixed-connection networks: arrays e alberi, sorting e counting, aritmetica intera.
3. Terza parte: Introduzione agli algoritmi randomizzati. Il metodo probabilistico. Strutture dati: hashing. Algoritmi probabilistici su grafi: all pairs shortest paths e minimum spanning trees.

Bibliografia

• Appunti delle lezioni.
• Cormen T.H., Leiserson C.E., Rivest R.L Introduction to Algorithms, and C.Stein MIT Press.
• Gusfield D., Algorithms on Strings, Trees and Sequences , Cambridge University Press, 1997.
• Motwani R. and Raghavan P. Randomized Algorithms Cambridge University Press, 1995.
• Quinn M.J.: Parallel computing - Theory and Practice, 2nd Ed. McGraw-Hill, 1994.

Modalità d'esame

L'esame consiste in una prova orale.

******************************************************************************

Aims

The main objective of the course is to deepen some of the topics studied in the course Algorithms and Data Structures, introducing problems and tools related to areas in which the theory of algorithms plays today a fundamental role. The chosen themes for this purpose are algorithms on strings and trees and related data structures, parallel algorithms and randomized algorithms. We will briefly mention, at the end of the course, to algorithms based on a symbolic representation of data. The vastity of the fields will allow, especially for the second and third part, only an introduction but the centrality, pervasiveness and elegance of the presented ideas justify and motivates the study.

The course will consist of three parts: in the first part we will study issues related with the design and use of string matching and complexity analysis of algorithms. In the second part the main parallel models and architectures together with the foundamental techniques for the analysis and the design of parallel algorithms will be presented. In the third part we will see the foundation of the theory of randomized algorithms, re-visiting known algorithms in their randomized version.

Program

1. First part: Introduction. The exact string matching: Knuth-Morris-Pratt, Rabin-Karp, Boyer-Moore algorithms. Suffix trees and applications, Ukkonen and McCreight algorithms, Harel-Tarjan algorithm for the lowest common ancestor determination. Aho-Coarsik algorithm. The problem of inexact string matching: Sellers, Landau-Vishkin, and Chang-Lawler algorithms.

2. Second part: Sorting networks: introduction, running time, bitoning and merging algorithms. Models and algorithms for parallel computers: the PRAM model, pointer jumping, Brent’s theorem, examples. Fixed-connection networks: arrays and trees, sorting and counting, integer arithmetic.

3. Third part: Introduction to randomized algorithms. The probabilistic method. Data structures: hashing. Probabilistic algorithms on graphs: all pairs shortest path and minimum spanning trees.

References

Class notes.
Cormen T.H., Leiserson C.E., Rivest R.L Introduction to Algorithms, and C.Stein MIT Gusfield D., Algorithms on Strings, Trees and Sequences , Cambridge University Press, Motwani R. and Raghavan P. Randomized Algorithms Cambridge University Press, 1995.
Quinn M.J.: Parallel computing - Theory and Practice, 2nd Ed. McGraw-Hill, 1994.