Unit ALGORITHMS AND DATA STRUCTURES
- Course
- Programming and management of computer systems
- Study-unit Code
- 55000606
- Curriculum
- In all curricula
- Teacher
- Francesco Betti Sorbelli
- Teachers
-
- Francesco Betti Sorbelli
- Hours
- 42 ore - Francesco Betti Sorbelli
- CFU
- 6
- Course Regulation
- Coorte 2026
- Offered
- 2026/27
- Learning activities
- Caratterizzante
- Area
- Tecnologie informatiche e dell'informazione
- Sector
- INFO-01/A
- Type of study-unit
- Obbligatorio (Required)
- Type of learning activities
- Attività formativa monodisciplinare
- Language of instruction
- Italian.
- Contents
- Fundamentals of algorithm analysis and asymptotic notation. Divide-and-conquer techniques and sorting algorithms. Heaps and priority queues. Elementary data structures, hash tables, binary search trees, red-black trees and disjoint sets. Graph representations, graph traversal, minimum spanning trees and shortest paths.
- Reference texts
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, fourth edition. Slides, exercises and supplementary materials are provided by the lecturer through the UniStudium platform.
- Educational objectives
- The course provides the fundamental knowledge required to understand, design and analyse algorithms and data structures. By the end of the course, students will be able to describe algorithms using pseudocode; assess their correctness and time complexity; solve simple recurrences; select suitable data structures; apply sorting, searching and dynamic-set algorithms; represent graphs and apply the main traversal, minimum spanning tree and shortest-path algorithms. Students will also be able to justify algorithmic choices and compare alternative solutions in terms of correctness and efficiency.
- Prerequisites
- Basic programming knowledge: variables, data types, expressions, control structures, functions, recursion and arrays. Basic mathematical knowledge, logical reasoning skills and familiarity with sets, functions, summations and logarithms are also required.
- Teaching methods
- The course consists of 42 hours of classroom teaching. Lessons combine theoretical concepts, pseudocode descriptions, correctness and complexity analysis, and guided examples and exercises. Particular attention is devoted to step-by-step algorithm execution and to comparing alternative data structures and solutions.
- Other information
- Slides, exercises and course announcements are available through the UniStudium platform. Attendance is recommended.
- Learning verification modality
- The examination consists of an individual written test lasting up to two hours, with no reference material allowed. The test includes exercises on algorithm analysis, execution of operations on data structures and application of the algorithms covered in the course, together with theoretical questions. Students may be required to show the main execution steps, justify their choices, identify the auxiliary structures used and determine asymptotic complexity. Assessment considers correctness, completeness of the solution process, analytical ability and appropriate use of terminology.
- Extended program
- 1. Algorithms, pseudocode, RAM model, correctness and loop invariants. Worst-case analysis and growth rates.
2. Insertion Sort, Merge Sort and the divide-and-conquer paradigm. Binary search.
3. O, O and T asymptotic notation. Growth functions. Recurrences, expansion method and Master Theorem.
4. Binary heaps, Heapify, heap construction, Heap Sort and priority queues.
5. Quick Sort: partitioning and analysis. Lower bound for comparison sorting. Counting Sort, Radix Sort and Bucket Sort.
6. Arrays, matrices, stacks, queues, linked lists and rooted trees.
7. Direct addressing and hash tables. Chaining, open addressing, linear probing and double hashing.
8. Binary search trees: traversal, search, minimum, maximum, successor, predecessor, insertion and deletion.
9. Red-black trees: properties, rotations and insertion.
10. Disjoint sets: Make-Set, Find-Set and Union; list and forest implementations, union by rank and path compression.
11. Graphs and their representations. Breadth-first search and unweighted shortest paths.
12. Depth-first search, edge classification, topological sorting and strongly connected components.
13. Minimum spanning trees, cut property, Kruskal’s and Prim’s algorithms.
14. Single-source shortest paths, relaxation, Bellman-Ford, shortest paths in DAGs and Dijkstra’s algorithm. - Obiettivi Agenda 2030 per lo sviluppo sostenibile
- Goal 4 – Quality Education. The course contributes to the development of scientific, digital and problem-solving skills.