ALGORITHMS Single channel
Chair (Coordinator) and Rapporteur: DANILO FRANCATI
Lecturers
Objectives
Educational goals
The course provides students with the theoretical and practical foundations of algorithm design and analysis. It covers the main algorithmic design paradigms, including greedy algorithms, divide-and-conquer techniques, and graph algorithms, while introducing computational complexity and computational tractability. By the end of the course, students will be able to analyse the correctness and efficiency of algorithms, compare alternative solution strategies, and design algorithmic solutions for medium-complexity computational problems.
Knowledge and understanding
Students acquire a solid understanding of the main algorithm design paradigms, fundamental data structures, and classical algorithms for optimisation, coding, scheduling, and shortest-path problems. They understand methods for analysing computational complexity and the principles underlying algorithm correctness.
Applying knowledge and understanding
Students are able to model computational problems, identify the most appropriate algorithmic strategy, design correct and efficient algorithms, analyse their time and space complexity, and compare alternative solutions according to their performance.
Making judgements
Students develop the ability to critically evaluate algorithms and data structures by identifying their strengths, limitations, and applicability. They are able to justify their design choices by considering correctness, efficiency, and problem constraints.
Communication skills
Students acquire the ability to describe algorithms and prove their correctness using appropriate technical language, pseudocode, and mathematical notation. They are also able to present clearly the design process and the complexity analysis of the proposed solutions.
Learning skills
Students develop independent learning skills that enable them to study new algorithms, design techniques, and theoretical results autonomously, applying the acquired knowledge critically to computational problems beyond those explicitly covered during the course.
Learning outcomes
1. Knowledge and understanding
Students will be able to describe and explain the main concepts, algorithms, and data structures used in the analysis and design of algorithms. They will be able to explain basic concepts and algorithm design strategies, applying their knowledge in concrete contexts.
2. Ability to apply knowledge and understanding
Students will be able to apply their knowledge to solve algorithmic problems, selecting and adapting appropriate solutions based on efficiency and correctness constraints, and evaluating trade-offs among different strategies.
3. Critical thinking and judgment
Students will be able to critically evaluate existing algorithms, assessing their correctness, computational complexity, execution time, memory usage, and scalability. They will be able to identify and understand fundamental properties of algorithms, such as correctness and optimality, and evaluate their suitability for specific contexts.
4. Communication skills
Students will be able to communicate algorithmic solutions clearly and rigorously, expressing ideas and concepts using pseudocode or appropriate technical language. They will be able to explain and justify their design choices to others, demonstrating the ability to present their work in a structured and understandable manner.
5. Learning skills
Students will be able to learn autonomously and reflect critically on their own learning in the field of algorithms. They will be able to identify gaps in their understanding, select areas for further study, and deepen their knowledge through independent research and exploration of new developments in the field.
Prerequisites
No formal prerequisites
Programme
Algorithms
Gale-Shapley
Heaps, Priority queues
Sorting
Greedy: Interval Scheduling, Interval Partitioning, Codici di Huffman, Shortests Paths
Dynamic Progamming: Weighted Interval Scheduling, Segmentation, Subset-Sum, Bellman-Ford
Introduction to approximation algorithms
Books
"Algorithm Design", Kleinberg, Tardos
"Introduction to Algorithms", Cormen, Leiserson, Rivest, Stein
Learning material provided by the instructor
Bibliography
"Algorithm Design", Kleinberg, Tardos
"Introduction to Algorithms", Cormen, Leiserson, Rivest, Stein
"Automata and computatability", Kozen
Lessons mode
The teaching activities of the course are based exclusively on lectures:
- During the lectures, the instructor presents (on the board and/or using slides) the fundamental theoretical concepts of algorithm design.
- Students are encouraged to actively participate in classroom discussions, ask questions, and solve exercises proposed by the instructor during the lecture to consolidate their understanding of the concepts.
Frequency
Attendance is not mandatory, but it is strongly recommended.
Exam mode
Written exam
- Type: individual test composed of open-ended questions and practical problems on algorithm analysis and design.
- Objectives: to verify the knowledge of fundamental theoretical concepts and the ability to design and analyze algorithms.
- Assessment criteria: correctness of the answers, clarity and completeness of explanations, correctness of the proposed algorithms, and ability to analyze their complexity and performance.
Final evaluation
- The grade is expressed on a 30-point scale.
- To pass the exam (18/30), the student must demonstrate sufficient knowledge of fundamental algorithm concepts and the ability to solve practical problems with correct algorithms and basic complexity analysis.
- To achieve the maximum grade (30/30 cum laude), the student must demonstrate an excellent understanding of the concepts covered in the course, be able to solve complex problems by proposing correct and efficient algorithms, and justify design choices with rigorous and complete explanations.
Example exam questions
1. Design an efficient algorithm for the multiplication of two integers, proving its correctness and analyzing its complexity.
2. Design an algorithm that finds the longest path in a DAG.
3. Prove that a tree with n nodes has exactly n-1 edges.
Arguments
- Intro on Algorithms
- The Gale-Shapley Algorithm
- Runtime Bounds and Asymptotic Notation
- Data Structures
- Greedy Algorithms
- Interval Scheduling
- Interval Partitioning
- Radio Transmitter Placement
- Graphs
- Dijkstra's Algorithm
- Heaps
- Priority Queues and Shortest Paths
- Prefix Coding
- Huffman's Algorithm (1)
- Huffman's Algorithm (2)
- Weighted Interval Scheduling
- Segmentation
- Subset Sum
- Bellman-Ford
- Divide-and-Conquer
- Integer Multiplication
- P and NP
- Vertex Cover
Sustainability goals
- Academic year2026/2027
- Degree program to which the course belongsApplied Computer Science and Artificial Intelligence
- Lesson code10629563
- Year and semester1st year - 2nd semester
- Activity typeBasic educational activities
- Academic areaFormazione informatica
- SSDINFO-01/A
- Mandatory presenceNo
- Languageeng
- CFU6 CFU
- Total duration60 hours
- Hours distribution36 classroom hours, 24 seminars hours