INFORMATICS II

The course introduces the fundamentals of algorithm design and analysis, with particular emphasis on fundamental data structures and algorithms on graphs and sorting. A section of the course is dedicated to the use of Python and the main scientific libraries for computational mathematics, with an introduction to Artificial Intelligence and Machine Learning concepts.

Knowledge and understanding: students will acquire knowledge of the main algorithm design techniques (incremental, divide-and-conquer), methods for analyzing algorithmic complexity, and the functioning of fundamental data structures (stacks, queues, trees, graphs). Basic concepts of regression and clustering will also be introduced.

Applying knowledge and understanding: students will develop skills in designing and implementing algorithms in Python, managing datasets with scientific libraries, and solving practical computational problems. They will also be able to apply supervised and unsupervised learning models to simple case studies.

Making judgements: students will gain the ability to select the most appropriate data structures and algorithms depending on the problem, evaluate the efficiency and limitations of proposed solutions, and critically interpret the results obtained.

Communication skills: students will acquire the ability to clearly and rigorously present algorithmic solutions and programming projects, including through code documentation and discussion of results.

Learning skills: students will be able to independently deepen their understanding of algorithms and AI techniques not covered in the course, using specialist literature and technical documentation, and apply the acquired knowledge to new contexts in computer science and mathematics.

Teaching organization
total study 150 hours
103 hours of individual study
35 hours of frontal lectures
12 hours of exercises

The course is articulated in frontal lectures and pratical classes

Attendance at classes is strongly recommended.

The course introduces the foundations of algorithm design and analysis, with practical applications to computer science and computational mathematics. The program is completed with an introductory section on Artificial Intelligence and Machine Learning, using Python and scientific libraries.

Algorithm design and complexity

• Algorithms as a technology for solving computational problems

• Design techniques: incremental methodology and divide-and-conquer

• Algorithm complexity and its practical implications

Fundamental data structures

• Stacks, queues, linked lists: definitions, basic operations, and implementation

• Hash tables: basic concepts and implementation

• Binary search trees: structure, basic operations, and implementation

Graphs and graph algorithms

• Graph definition: directed and undirected

• Representations and implementation (adjacency lists, matrices)

• Traversals: BFS (Breadth-First Search) and DFS (Depth-First Search) – definition and implementation

• Shortest-path algorithms:

  • Dijkstra – description and implementation

  • Bellman-Ford – description and implementation

Analysis of recursive algorithms and sorting

• Solving recurrences:

  • Substitution method

  • Iterative method and recursion-tree method

  • Master theorem

• Sorting algorithms:

  • MergeSort, QuickSort – description and implementation

  • Linear-time sorting: Counting Sort, Radix Sort – description and implementation

• Medians and order statistics: linear-time selection algorithm – description and implementation

Laboratory: Python for computational mathematics

• Introduction to Python for scientific computing

• Use of main libraries:

  • NumPy: arrays, vector/matrix operations

  • SciPy: linear algebra, integrals, optimization

  • Pandas: simplified dataset management in tabular form

Introduction to Artificial Intelligence and Machine Learning

• Historical background and motivations of AI

• Learning paradigms:

  • Supervised learning

  • Unsupervised learning

• Basic algorithms:

  • Linear regression: model, cost function, optimization – and implementation

  • Clustering (k-means): distance, centroid, iterative algorithm – and implementation

T. H Cormen

Introduction to Algorithms

The MIT Press 

To sit for the final exam, you must have booked on the SmartEdu portal. For any technical issues regarding your booking, 
please contact the Segreteria Didattica.

The first part is a practical exam on arguments treated in the course, in Python. 

The second part consists of a project on the argument studied in class. 

The verbalization will be preceded by a brief discussion on the results of the two tests and, in dubious cases, by a short oral test. 

Final grades will be assigned taking into account the following criteria:

Rejected: Basic knowledges have not been acquired. The student is not able to solve simple exercises and implement simple Python programs. 

18-23: Basic knowledges have been acquired. The student solves simple exercises and has a moderate ability of implementing simple Python programs.

24-27: All the knowledges have been acquired. The student solves all the proposed exercises and implements the requested program making few errors. 

28-30 cum laude: All the knowledges have been completely acquired. The student applies knowledge and has excellect communication skills, learning skills and making judgements.