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.
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.