Unit ALGORITHMS AND DATA STRUCTURES WITH LAB

ALGORITHMS AND DATA STRUCTURES WITH LAB - I MODULE

Code	55100609
CFU	6
Teacher	Maria Cristina Pinotti
Teachers	Maria Cristina Pinotti
Hours	52 ore - Maria Cristina Pinotti
Learning activities	Caratterizzante
Area	Formazione scientifico-tecnologica
Sector	INF/01
Type of study-unit	Obbligatorio (Required)
Language of instruction	Italian
Contents	Design and analysis of algorithms. Sorting algorithms with/out comparisons. Selection. Heapsort. Binary Search Trees. Divide-et-impera.
Reference texts	T. H. CORMEN, C. E. LEISERSON, R. L. RIVEST, C. STEIN Introduction to algorithms, McGraw-Hill, 2010, ISBN-13: 978-0262533058 Instructional materials used during lectures are, usually, also made available on Unistudium.
Educational objectives	The course provides the basic algorithmic skills that are characteristic for the course of study. The main objective of the course is to provide students with the basis for understanding, evaluating, and proposing deterministic algorithms, similar to those studied in the course, but extended to new contexts. The main knowledge acquired will be: the ability to evaluate the efficiency of an algorithm; algorithms for sorting; use of data structures.
Prerequisites	Elements of Calculus, Discrete Mathematics and a programming language.
Teaching methods	Lectures in class.
Other information	Attendance is expected. Nonetheless, all the arguments we deal with are widely discussed in the suggested textbooks.
Learning verification modality	There is a single exam for Modulo I and Modulo II of Algorithms and data structures. The test is written, but the student can ask a supplemental oral test. The written test requires solving exercises aimed at measuring the ability to apply acquired knowledge to new contexts. The oral examination covers all course content program and consists both in questions about the theory and in the solution of exercises. Its length is about 20-25 minutes. The final grade is based on both grades in the written and oral examinations. The oral test is not mandatory if the written test is sufficient. The students that regularly attend the class can take two partial exams. The students can ask for a supplemental oral exam as well. In case the student intends to advance the examination in a year prior to the one scheduled in the study plan, it is recommended to attend the lecture series and to take the exam in the first useful call after the lectures are finished, thus respecting the semester of the teaching schedule.
Extended program	Mathematical Foundations. Principles for evaluating algorithms: correctness, space and time complexity in the worst and average case. Divite-et-impera. Recurrences. Master Theorem for solving basic recurrences. Sorting algoritms: InsertionSort, QuickSort, MergeSort, HeapSort, CountingSort, RadixSort. Lower bound techniques. Lowerbound for sorting based on comparisons.Selection in linear time. Graphs: representation, depth first search and breadth first search. Directed and undirected graphs. Directed acyclic graph. Topological order.Several implementation of the Dijkstra algorithm. Algorithms for Minimum Spanning Tree. Mention shortest path among all the pairs of vertices.
Obiettivi Agenda 2030 per lo sviluppo sostenibile	This teaching contributes to the realization of the UN goals of the 2030 Agenda for Sustainable Development.

ALGORITHMS AND DATA STRUCTURES - II MODULE

Code	55107606
CFU	6
Teacher	Francesco Betti Sorbelli
Teachers	Francesco Betti Sorbelli
Hours	47 ore - Francesco Betti Sorbelli
Learning activities	Caratterizzante
Area	Formazione scientifico-tecnologica
Sector	INF/01
Type of study-unit	Obbligatorio (Required)
Language of instruction	Italian.
Contents	Directed and undirected graphs and their representations. Breadth-first and depth-first traversal. Directed acyclic graphs, topological sorting and strongly connected components. Minimum spanning trees. Single-source and all-pairs shortest paths in weighted graphs. Correctness and complexity analysis of algorithms.
Reference texts	T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, third edition, MIT Press, 2009. M. T. Goodrich, R. Tamassia, Algorithm Design and Applications, Wiley, 2015. Slides, exercises and supplementary materials are provided through the UniStudium platform.
Educational objectives	The module provides the knowledge and skills required to understand, apply and analyse the main graph algorithms. By the end of the module, students will be able to select a suitable graph representation; apply traversal, connectivity, topological sorting, minimum spanning tree and shortest-path algorithms; identify the applicability conditions of each algorithm; analyse correctness and complexity; and compare alternative solutions according to graph characteristics. Students will also be able to adapt the algorithms studied to problems arising in new contexts.
Prerequisites	Knowledge of programming using an imperative language, discrete mathematics and basic mathematical analysis. Knowledge acquired in Module I is also required: complexity analysis, asymptotic notation, recurrences, sorting, heaps, priority queues and disjoint-set data structures.
Teaching methods	The module consists of 47 hours of lectures and exercise sessions. Lessons combine theoretical concepts, pseudocode descriptions, correctness and complexity analysis, and guided exercises. Particular attention is devoted to step-by-step algorithm execution and to selecting the most appropriate solution according to graph characteristics.
Other information	This module is part of the integrated course “Algorithms and Data Structures with Laboratory” and cannot be taken independently of Module I. Teaching materials and course announcements are available through the UniStudium platform. Attendance is recommended.
Learning verification modality	Assessment is integrated with Module I. The examination consists of a written test and, where applicable, an oral examination. The written test includes exercises designed to assess the ability to apply the algorithms covered in the course, show their main execution steps, justify the choices made and determine their complexity. The oral examination, when taken, covers both modules and includes theoretical questions and the discussion of exercises. Assessment considers solution correctness, the ability to apply knowledge to new contexts, quality of analysis and clarity of presentation.
Extended program	1. Fundamental definitions and properties of directed and undirected graphs. Weighted graphs. 2. Graph representation using adjacency lists and matrices. Analysis of representation costs. 3. Breadth-first search, BFS trees and shortest paths in unweighted graphs. 4. Depth-first search, DFS forests, discovery and finishing times, and edge classification. 5. Directed acyclic graphs and topological sorting. 6. Connected components and strongly connected components. 7. Disjoint-set data structures and their application to graph algorithms. 8. Minimum spanning trees and the cut property. Kruskal’s and Prim’s algorithms. 9. Single-source shortest paths. Optimal substructure, relaxation and shortest-path trees. 10. Bellman-Ford algorithm and negative-weight cycle detection. 11. Shortest paths in directed acyclic graphs. 12. Dijkstra’s algorithm and its implementation using priority queues. 13. All-pairs shortest paths in weighted graphs. 14. The matrix-multiplication-based algorithm and its accelerated version. 15. Floyd-Warshall algorithm and transitive closure. 16. Johnson’s algorithm for sparse graphs. 17. Comparison of shortest-path algorithms, applicability conditions and complexity analysis.
Obiettivi Agenda 2030 per lo sviluppo sostenibile	Goal 4 – Quality Education. The module contributes to the development of scientific, digital, analytical and problem-solving skills.