INFORMATICA 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

If the course is delivered in blended or remote mode, appropriate adjustments may be made to the above, in order to ensure consistency with the syllabus.
 

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

Thomas H. Cormen et al., 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. 

Learning assessment may also be carried out on-line, should the conditions require it. To ensure equal opportunities and in compliance with current laws, interested students may request a personal interview in order to plan any compensatory and/or dispensatory measures based on educational objectives and specific needs. Students can also contact the CInAP (Centro per l'integrazione Attiva e Partecipata – Servizi per le Disabilità e/o i DSA) referring teacher within their department (https://www.cinap.unict.it/content/referenti).

Asymptotic Complexity
*"Given the recurrence $T(n)=4T(n\mathrm{/}2)+O(n)$T(n)=4T(n/2)+O(n), determine which case of the Master Theorem applies and write the asymptotic solution."*

Sorting Algorithms
"Describe the worst case of QuickSort: in which input configuration does it occur, what is the resulting complexity, and how does the randomized choice of pivot mitigate the problem?"

Data Structures
"Explain the difference between adjacency list and adjacency matrix for graph representation: state the space complexity and the cost of the main operations, motivating the choice based on graph density."

Graphs — Traversals
"Perform a BFS traversal on the following graph starting from node A, indicating step by step the state of the queue, the set of visited nodes, and the computed distances."

Python Programming — OOP
"Implement in Python a base class Shape with a color attribute and a subclass Rectangle that overrides the describe() method and adds an area() method. Use super().__init__() in the subclass constructor."

Scientific Libraries
"Using NumPy, create an array of 10 random elements, compute its mean and standard deviation, and select the elements greater than the mean."