Computer and Control Engineering

SILVIA BONOMI
GIUSEPPE ANTONIO DI LUNA

General objectives:
Knowledge of the fundamental algorithms and data structures. Ability to both implement them in a modern programming language (Java or C) and to make design choices to solve real problems in application domains. Knowledge of aspects related to the computational cost of algorithms. Ability tto design algorithms for the solution of new problems, using or modifying algorithms and data structures seen during lessons.

Specific objectives:
Ability to:
- design/implement algorithmic solutions based on known techniques or simple variants;
- to approximately evaluate the computational resources necessary for an algorithmic solution;
- make informed design choices for problem solving.

Knowledge and understanding:
Knowing the fundamental data structures and algorithms. Understanding the concepts of correctness and computational cost of an algorithm. Knowing the main paradigms for designing algorithms.

Apply knowledge and understanding:
Being able to design an algorithm that solves a problem and implement it in modern programming language.

Critical and judgment skills:
Being able to assess the correctness, adequacy and efficiency of the algorithmic solution of a problem.

Communication skills:
Being able to effectively describe the requirements of a problem and provide to third parties the relative specifications, design choices and
the reasons underlying these choices.

Learning ability:
The course will allow the development of skills for the independent study of topics related to the course. It will also allow the student to
easily consult advanced and/or specific manuals for autonomous learning of ad-hoc algorithmic solutions.

Knowledge and understanding
At the end of the course, students will be familiar with the main data structures and fundamental algorithms, understanding their functioning, properties, and typical application contexts. Students will also know the main algorithm design paradigms, including divide and conquer and dynamic programming, and understand their role in solving computational problems.

Applying knowledge and understanding
Students will be able to apply appropriate data structures and algorithmic techniques to the solution of computational problems. They will also be able to design algorithms based on the paradigms studied and use them to solve problems of moderate complexity.

Making judgements
Students will be able to analyze and evaluate algorithms and data structures, verifying their correctness and analyzing their computational complexity. They will also be able to compare alternative algorithmic solutions and select the most appropriate one for a given problem.

Communication skills
Students will be able to describe and discuss algorithms and data structures using appropriate technical terminology, clearly explaining their functioning, properties, and efficiency.

Learning skills
Students will acquire methodological tools to approach new algorithmic problems and to autonomously deepen their knowledge of more advanced techniques for algorithm design and analysis.

None.
A certain familiarity with at least one programming language, between C and Java, is recommended.

2.1 Part I: Introduction to the Course and Fundamental Concepts
- Introductory examples and algorithm analysis. Basic operations and algorithm complexity. Analysis of algorithms and programs: uniform-cost RAM model. Input size. First examples of complexity analysis of algorithms and programs. Worst-case analysis and an introduction to average-case analysis. Beyond the worst case: aggregate analysis of sequences of operations.

- Cost analysis of algorithms and asymptotic notation. Growth of functions. Notations O, Ω, and Θ. Notations o and ω. Additional examples of algorithm analysis.

- Divide-and-Conquer method. First examples. Recurrences and analysis of recursive algorithms. Solving recurrences: substitution method and recursion tree method with examples. Brief introduction to the master theorem.

2.2 Part II: Sorting and Selection

- Sorting and Merge Sort. The sorting problem. Divide-and-conquer-based sorting: Merge Sort. Analysis of correctness and computational cost of Merge Sort. Quicksort. Other examples of the Divide-and-Conquer method. Analysis of correctness and computational cost of Quicksort.

- Sorting complexity. Lower bound on comparison-based sorting algorithms: illustration and proof. Non-comparison-based algorithms and linear-time sorting: Counting Sort, Radix Sort, and Bucket Sort.

- The selection problem. Introduction: finding the minimum and maximum. Algorithms for linear-time selection. Randomized selection with expected linear time and linear-time worst-case selection. Introduction to expected-time analysis for randomized selection. Analysis of linear-time worst-case selection.

2.3 Part III: Graphs and Fundamental Data Structures
- Data Structures: Heaps and Priority Queues. Operations and desired complexity. Applications: efficient implementation of Dijkstra's algorithm, Heapsort, and computation of the top-k elements. Heap implementation using arrays. Heapify. Resizing heaps implemented with arrays. Aggregate analysis of sequences of operations on array-based heaps (see also references related to resizing hash tables).

- Introduction to Graphs. The concept of a graph. Directed and undirected graphs. Basic terminology and properties. Graph representations. Adjacency lists, adjacency matrices, and their costs.

- Graph traversal and applications. Breadth-First Search (BFS) and shortest paths in unweighted (directed or undirected) graphs. Depth-First Search (DFS) in directed and undirected graphs and its properties. Edge classification. Topological sorting in directed graphs: applications and conditions for existence. Algorithms for topological sorting based on DFS. Connected components and reachability. Strongly connected components in directed graphs. Computation of strongly connected components using DFS: linear-time algorithm (Kosaraju’s algorithm).

- Shortest paths and Dijkstra's algorithm. Single-source shortest path problem in weighted graphs. BFS and shortest paths: why BFS does not work in weighted graphs. Shortest paths in weighted graphs: properties of shortest paths and relaxation. Dijkstra’s algorithm: correctness and computational cost. Bellman-Ford algorithm: correctness and computational cost.

- Greedy method and Minimum Spanning Trees. Minimum spanning tree problem. Prim's algorithm: correctness and computational cost. Efficient version using heaps. Kruskal’s algorithm. Efficient implementation of Kruskal’s algorithm using Union-Find. Correctness analysis of Kruskal’s algorithm.

- Data Structures: Hash Tables. Operations and desired complexity. Applications. Hash functions and hash table implementation. Collision resolution: chaining and open addressing. Main techniques of open addressing. Load factor and hash table resizing: aggregate analysis of sequences of insertions and deletions.

- Data Structures: Binary Search Trees. Ordered arrays and search trees. Main operations on ordered arrays and binary search trees, and their cost. Implementation of binary search trees. Balancing: maintenance and rotations after insertions and deletions. Introduction to balanced search trees: red-black trees and their height.

- Data Structures: Disjoint Set Maintenance. Operations on disjoint sets. Representation of disjoint sets with linked lists. Representation of disjoint sets with forests.

2.4 Part IV: Algorithmic Techniques
- Greedy approach to algorithm design. Huffman algorithm. The greedy paradigm: introductory examples. Codes and Dynamic Programming. Introductory examples: problems and algorithm design using the dynamic programming paradigm. More complex examples: the knapsack problem.

-Dynamic Programming and Shortest Paths. All-pairs shortest paths and dynamic programming: Floyd-Warshall algorithm. Transitive closure of a graph.

Main text
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduzione agli Algoritmi e
Strutture Dati - IV edizione. McGraw Hill, Milano, Italia, 2023.

Alternative Books
Tim Roughgarden: Algorithms Illuminated Omnibus Edition, 2022. Sito Web del libro con materiale: https://www.algorithmsilluminated.org/
Robert Sedgewick and Kevin Wayne. Algorithms, 4th Edition. Addison-Wesley,

The course is given fully in person with direct lectures and laboratory activities.

Attendance is not mandatory, although it is strongly recommended.

The exam consists of a series of open-ended questions and a programming test.

To pass the exam, students must achieve a minimum grade of 18/30.
Students must demonstrate sufficient knowledge of the main data structures and fundamental algorithms, a basic understanding of the algorithm design techniques covered in the course (including divide and conquer and dynamic programming), and the ability to analyze the functioning of simple algorithms, evaluate their correctness, and discuss their computational complexity, applying these tools to the solution of basic problems.
To achieve a grade of 30/30 with honors, students must demonstrate excellent knowledge of all the topics covered in the course, showing full mastery of the data structures and algorithmic techniques studied, and being able to analyze, compare, and design efficient algorithmic solutions, rigorously discussing their correctness and complexity while connecting the different concepts logically and coherently.

Minimum Spanning Trees. Let G = (V, E) be an undirected, connected graph with positive edge weights. In particular, for (u, v) ∈E, let w(u, v) denote the weight of edge (u, v). Given this:
(a) [2 points] Formally define the problem of finding a minimum spanning tree in G.
(b) [2 points] Formally prove that if (u, v) is an edge of minimum weight in G, then there exists at least one minimum spanning tree in G that contains (u, v).
Hint: It is recommended to proceed by contradiction.

The score will depend greatly on the rigor, clarity of exposition, and the strength of the arguments presented. It is not necessary to write a lot, but to write well.