Computer and Control Engineering

LUCA BECCHETTI

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.

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.
Ability to design algorithms for solving new problems, using, repurposing or modifying known algorithms and/or data structures seen in class.

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 complexity of an algorithm. Knowing the main algorithimic design paradigms.

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 of basic mathematical notions and calculus, corresponding to the topics of an introductory course in Calculus
Knowledge of key notions from probability theory, corresponding to the topics covered by an introductory course in Probability
Basic programming skills, knowledge of elementary data structures and ability to implement them, corresponding to an introductory course in Programming and elementary data structures

1. Recursion

2. Introduction: uniform cost model and its limits
2.1. Cost models for algorithm analysis: uniform cost model
2.2. Worst-case and asymptotic analysis

3. Sorting and Selection
3.1. Introduzione della tecnica divide-and-conquer
3.2. Merge-Sort and Quick-Sort
3.3. Sorting: lower bounds
3.4. Linear sorting algorithms: Bucket Sort e Radix Sort
3.5. The Selection problem. Linear time sorting algorithms


4. Algorithm design: basic techniques
4.1. Greedy algorithms
4.2. Divide and Conquer
4.3. Dynamic programming


5. Data structures
5.1. Priority queues and heaps
5.2. Maps
5.3. Hash functions and hash tables
5.4. Sorted maps: binary search trees


6. Directed and undirected graphs: representation and algorithms
6.1. Algorithms for graph visit
6.2. Connected components and other application of depth and breadth visit algorithms
6.3. Shortest paths: problems and algorithms
6.4. Minimum spanning trees: problem and algorithms
6.5. Union Find



7. String algorithms
7.1. Pattern matching: Boyer-Moore and Knuth-Morris-Pratt's algorithm
7.2. Compression and Huffman'a algorithm
7.3. DNA sequencing



8. Randomization
8.1. Quicksort and Quickselect
8.2. Primality test
8.3. Efficient randomized algorithms for primality test

- Adopted textbook: 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.
- Suggested as an alternative textbook (in English): Tim Roughgarden. Algorithms Illuminated - Omnibus Edition. Soundlikeyourself Publishing LLC, New York, NY, 2022.

Lectures will be held in presence. Part of the lectures will be applied, with the students involved, together with the instructor, in implementing notions and concepts introduced in the course

Attendance is not mandatory

To pass the exam, students need to receive a grade 18/30 or higher.
They must show a fair knowledge of the main data structures problems and algorithms to solve them that were taught in the course. They further need to possess an at least basic knowledge of more advanced topics on graphs, in particular the main problems studied and the main algorithmic strategies to solve them. They finally need to able to design and analyze algorithms to solve simple variants of problems seen in class or simple instances of new problems that can be solved using techniques seen in class.
To achieve a grade of 30/30 cum laude, students need to show that they achieved full command of all topics taught in the course, being able to connect and organize them in a logical and coherent way.

1.
Consider the following array A: 4 13 7 1 8. Describe the evolution of the Heap-Sort algorithm starting from array A, showing the tree that represents the max-heap at the end of every Max-Heapify call.

2.
Given a set S of n integers ranging from 1 to K; the set S must be partitioned into two subsets, S1​ and S2​, such that W1​ and W2​, the sums of the elements in subsets S1​ and S2​ respectively, are as close as possible to each other. Equivalently, the task is to find the partition that minimizes ∣W1​−W2​∣, the absolute value of the difference between W1​ and W2​.
(a) Write the pseudo-code for an efficient algorithm that, given S as input, returns a pair of sets S1​ and S2​ that represent a partition of S and satisfy the stated condition.
(b) Calculate the complexity of the proposed algorithm.

• Introduction and fundamental concepts


• Sorting and Selection


• Graphs and other fundamental data structures


• Algorithmic techniques