Vai al Contenuto Vai alla navigazione del sito

# FUNDAMENTALS OF ALGORITHMS (468SM)

#### A.A. 2019 / 2020

Docenti
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";
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