Algorithms and data structures

A.Y. 2014/2015
Lesson for
12
Max ECTS
120
Overall hours
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

Linea Milano
Active edition
Yes
Responsible
Laboratories: 48 hours
Lessons: 72 hours
Shifts:
Turno A
Professor: Lonati Violetta
Syllabus
Theory
Intuitive notions of problems and algorithms. Design and analysis of an algorithm. The RAM machine model and the corresponding uniform and logarithmic cost criteria.
Mathematical notions: elementary combinatorial structures, asymptotic notations, evaluation of sums, recurrence equations. Main data structures: arrays, lists, stacks, queues. Graphs, trees and their representations. Algorithms for visiting graphs and trees; depth-first search and breadth-first search.
Sorting algorithms: insertionsort, heapsort, quicksort. Divide and Conquer algorithms and the corresponding analysis of time complexity: mergesort, binary search, product of integers.
Abstract data structures and efficient implementation. Hash tables. Binary search trees. Balanced trees: B-trees. "Union-find" operations on partitions: algorithms based on trees with balancing and compression.
Dynamic Programming algorithms: transitive closure of graphs and (all pair) shortest paths. Greedy techniques: independent sets, matroids, Rado's theorem; algorithms for the minimum spanning tree (Kruskal, Prim) and for shortest paths from a source (Dijkstra).
Classification of problems. The classes P and NP. Introduction to NP-complete problems.

Laboratory
The course focuses on language C and its use in the implementation of data structures and algorithms.
Language C:
Introduction to C, an overview. Lexical analysis, primitive data types. Expressions, control flow. Functions. Array, pointers and strings. Structures and unions. Input and output. Standard Library.
Data Structures and Algorithms:
Recursion, Sorting algorithms, Divide et Impera, Backtracking, Dynamic Programming, Lists, Binary Search Trees, Red-Black Trees, Graphs.
Lesson period
First semester
Lesson period
First semester
Assessment methods
Esame
Assessment result
voto verbalizzato in trentesimi