Algorithms and Data Structures
A.Y. 2018/2019
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.
Expected learning outcomes
Undefined
Lesson period: First semester
Assessment methods: Esame
Assessment result: voto verbalizzato in trentesimi
Single course
This course cannot be attended as a single course. Please check our list of single courses to find the ones available for enrolment.
Course syllabus and organization
Single session
Responsible
Lesson period
First semester
ATTENDING STUDENTS
Course 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
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
Website
NON-ATTENDING STUDENTS
Course 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
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
Professor(s)