In this course, the students will learn basic techniques for the design and analysis of algorithms.

Knowledge and understanding: basic algorithms and data structures that are the main building blocks of more advanced methods (sorting, graph traversals, search trees); general techniques for algorithmic design and analysis (divide et impera, dynamic programming).

Applying knowledge and understanding: being able to identify the most suitable techniques to solve algorithmic problems and correctly apply them. Being able to read a scientific paper about algorithms, understand, and properly present it by using the opportune terminology.

Making Judgement: being capable of applying and combine algorithmic techniques in a critical way, identifying the most effective approaches to solve a given problem. Being able to critically compare different methods to evaluate their effectiveness.

Communication skills: being able to explain the basic ideas of algorithms and communicate the results to a learned public.

Learning skills: being capable of exploring the literature of algorithms to find alternative approaches and combine them to solve complex problems.

Basic knowledge of an imperative programming language. Difference between abstract and concrete data structure. Arrays, lists, stacks, queues.

Algorithms and data structures. Definition of algorithm. Computational models.

Matrix multiplication: Strassen's algorithm.

Binary search and sorting algorithms: insertion sort, quick sort, heap sort, merge sort.

Lower-bound for comparison-based sorting algorithms.

Linear sorting: counting sort, radix sort.

Graphs: definition, reachability, depth-first search and breath-first search. Single-source shortest path
problem and Dijkstra's algorithm. All-pairs-shortest paths problem and Floyd-Warshall's algorithm.

Cormen, Thomas; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford.
Introduction to Algorithms. MIT Press and McGraw-Hill

Algorithms and data structures. Definition of algorithm. Computational models.

Matrix multiplication: Strassen's algorithm.

Binary search and sorting algorithms: insertion sort, quick sort, heap sort, merge sort.

Lower-bound for comparison-based sorting algorithms.

Linear sorting: counting sort, radix sort.

Graphs: definition, reachability, depth-first search and breath-first search. Single-source shortest path
problem and Dijkstra's algorithm. All-pairs-shortest paths problem and Floyd-Warshall's algorithm.

Frontal and interactive lectures. During the lectures, non-compulsory homework exercises will be given to help understanding of the course's topics.

-

The exam will consist of a written theory test. The students will be required to: - give formal definitions of the problems seen in class - state and justify the computational complexity of the studied algorithms - compare different solutions to the same problem - provide simple examples and/or simulate some steps of the algorithms on the examples - describe the algorithms seen in class. The written test will be given a grade on the scale of 30s. Laude can be given for an exceptional exam, in which the student demonstrates a deep understanding of the concepts and is able to exhibit them clearly and concisely.

Questo insegnamento approfondisce argomenti strettamente connessi a uno o più obiettivi dell’Agenda 2030 per lo Sviluppo Sostenibile delle Nazioni Unite