Algorithms and data structures

A.Y. 2018/2019
Lesson for
6
Max ECTS
48
Overall hours
SSD
INF/01
Language
Italian
Learning objectives
Il corso ha l'obiettivo di introdurre i concetti fondamentali degli algoritmi e delle strutture dati, l'analisi della complessità degli algoritmi, le strutture dati elementari (i.e., liste, stack, coda, dizionario), la struttura dati albero, la struttura grafo, il problema dell'ordinamento, e la progettazione di algoritmi.

Course structure and Syllabus

Active edition
Yes
Responsible
INF/01 - INFORMATICS - University credits: 6
Lessons: 48 hours
Professor: Foresti Sara
ATTENDING STUDENTS
Syllabus
1- Basic concepts
Problem and algorithm; analysis of algorithms, space and computational complexity, asymptotic notations, analysis of algorithms complexity; complexity classes

2- Elementary data structures
Stack, code, list: definitions and operations, implementation using arrays and pointers; hash tables

3- Trees
Definition of tree, main operations over trees, representation of treesM binary search trees: definition, representation, operations; balanced binary trees

4- Graphs
Definition of graph, representation of graph; breadth first search and depth first search, concept of connected components; minimum spanning tree; the shortest path problem

5- Sort algorithms
The sorting problem; sort algorithms: insertion sort, merge sort, heap sort, quick sort (and its analysis); sorting in linear time

6- Algorithm design techniques [hints]
Divide-et-impera; greedy algorithms; dynamic programming
NON-ATTENDING STUDENTS
Syllabus
1- Basic concepts
Problem and algorithm; analysis of algorithms, space and computational complexity, asymptotic notations, analysis of algorithms complexity; complexity classes

2- Elementary data structures
Stack, code, list: definitions and operations, implementation using arrays and pointers; hash tables

3- Trees
Definition of tree, main operations over trees, representation of treesM binary search trees: definition, representation, operations; balanced binary trees

4- Graphs
Definition of graph, representation of graph; breadth first search and depth first search, concept of connected components; minimum spanning tree; the shortest path problem

5- Sort algorithms
The sorting problem; sort algorithms: insertion sort, merge sort, heap sort, quick sort (and its analysis); sorting in linear time

6- Algorithm design techniques [hints]
Divide-et-impera; greedy algorithms; dynamic programming
Lesson period
First semester
Lesson period
First semester
Assessment methods
Esame
Assessment result
voto verbalizzato in trentesimi
Professor(s)