Algorithms and data structures

A.Y. 2018/2019
Lesson for
12
Max ECTS
120
Overall hours
SSD
INF/01
Language
Italian
Learning objectives
Il corso consiste di una parte di teoria e una di laboratorio. Obiettivo della prima parte è quello di presentare le strutture dati e gli algoritmi di base ponendo l'enfasi sui metodi di progettazione sull'analisi delle procedure. La parte di laboratorio ha invece come obiettivo la presentazione del linguaggio C e il suo utilizzo nella implementazione di strutture dati e algoritmi.

Course structure and Syllabus

Milan
Active edition
Yes
Responsible
INF/01 - INFORMATICS - University credits: 12
Laboratories: 48 hours
Lessons: 72 hours
Shifts:
Parte seconda - turno unico
Professor: Lonati Violetta
Prima parte - Turno A
Professor: Lonati Violetta
Prima parte - Turno B
Professor: Lonati Violetta
Syllabus
The concept of Algorithm. Algorithms and programs. Asymptotic notations. Algorithm complexity.
The RAM Machine.
Fundamental data structures: array, list, stack, queue, tree.
Search: sequential and binary search. Tree structures for search.
Hashing.
Elementary sorting techniques. Advanced sorting techniques (mergesort, heapsort, quicksort).
Sorting techiques not using comparisons.
Fundamental algorithmic techniques: divide-and-conquere, dynamic programming, greedy.
Graphs.
Fundamental problems and algorithms on graphs: minimum spanning tree, minimal paths in graphs.
Hard problems: nondeterministic algorithms and NP-completeness (an introduction).

A detailed list of topics presented in each lecture is published and updated on the course webpage.
Lesson period
First semester
Lesson period
First semester
Assessment methods
Esame
Assessment result
voto verbalizzato in trentesimi