Vai al Contenuto Vai alla navigazione del sito

FUNDAMENTALS OF ALGORITHMS (468SM)

A.A. 2019 / 2020

Periodo 
Secondo semestre
Crediti 
6
Durata 
48
Tipo attività formativa 
Affine/Integrativa
Percorso 
[PDS0-2018 - Ord. 2018] comune
Mutuazione 
MUTP: SM35 - 587SM-2 - ALGORITHMIC DESIGN
Syllabus 
Lingua insegnamento 

INGLESE

Obiettivi formativi 

At the end of this module, students are expected to be able to:
* evaluate the asymptotic complexity of a known algorithm;
* design an efficient algorithm for simple problems;
* have a picture of the most efficient algorithms in pattern matching
and graph "analysis";
* read a scientific paper about algorithms, understand, and
properly present it by using the opportune terminology.

Prerequisiti 

The notions of set and function. Basic knowledge of any imperative language.

Contenuti 

Definition of algorithm. Computational model. Asymptotic analysis. Basic data structure. Sorting
algorithms. Select problem. Matrix multiplication. Graphs: definition, reachability, depth-first and breath-first visits. Strongly connected
components and topological sort. Graph transitive closure. Single source shortest path problem. All-pairs-shortest-path problem. Routing problem. Pattern matching problem. Suffix trees and suffix array.

Metodi didattici 

Frontal lessons and demo sessions.

Programma esteso 

Definition of algorithm. Computational
model. Asymptotic analysis. Basic data structure: array, matrix, list, queue, and list. Sorting algorithms: insertion sort, quick sort, heap sort. Select problem. Matrix multiplication and Strassen's algorithm. Graphs: definition, reachability, depth-first and
breath-first visits. Strongly connected components and topological sort:
Tarjan's algorithm. Graph transitive closure. Single source shortest
path problem and Dijkstra's algorithm. A* Algorithm. All-pairs-shortest-path problem and Floyd-Warshall's
algorithm. Routing problem and contraction hierarchies. Pattern matching problem: Knuth-Morris-Pratt's algorithm and Boyer-Moore-Galil's algorithm. Suffix trees and suffix array.

Modalità di verifica dell'apprendimento 

Coding homework and written and oral exam.

Testi di riferimento 

Cormen, Thomas; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford. Introduction to Algorithms. MIT Press and McGraw-Hill.


Torna all'elenco insegnamenti