ALGORITHMS AND DATA STRUCTURES
cod. 07563

Academic year 2022/23
1° year of course - Second semester
Professor
- Vincenzo BONNICI - Andrea MUNARO
Academic discipline
Informatica (INF/01)
Field
Discipline informatiche
Type of training activity
Characterising
72 hours
of face-to-face activities
9 credits
hub:
course unit
in ITALIAN

Learning objectives

The main aim of the course is to introduce the most common data structures and related algorithms. The course also aims at providing students with the ability to study the computational complexity of algorithms. Finally, the course develops analytical and abstraction skills and it aims at improving the ability related to the algorithmic solutions of problems.

With reference to Dublin indicators:

Knowledge and understanding
During the course, the main ideas related to algorithms and data structures are introduced. Students are encouraged to learn the study of computational complexity of algorithms and to learn proper use of different data structures.

Applying knowledge and understanding
Acquired theoretical knowledge is applied to solve specific problems. During the course, some exercise sessions are dedicated to the solutions of problems.

Making judgments
Exercises proposed during classes can be solved individually or in groups and they often can be solved in different ways. Students can compare their approach to the solutions proposed by other students and to the solutions shown during classes. Such comparisons enhance the development of specific skills which are useful to better understand the considered problems.

Communication skills
Discussions during classes allow students to improve their communications skills. Such discussions concern specific algorithmic techniques to solve the proposed problems and they focus on advantages and disadvantages of the proposed approaches. Students learn to work individually and in groups.

Learning skills
The study of algorithmic techniques and their application to heterogeneous problems help students to improve in-depth comprehension of the topics. Acquired knowledge can be adapted to solve problems which may be different from those specifically seen during classes. Students acquire computational techniques useful to work in groups and autonomously.

Prerequisites

Basic notions on mathematical analysis and programming.

Course unit content

The course introduces basic notions related to algorithms and data structures. In particular, the study of the computational complexity of algorithms is investigated and correct algorithms for different data structures are studied.

Full programme

Introduction to the study of algorithms and data structures

Study of the computational complexity of algorithms

Algorithms for arrays (e.g., search and sorting)

Algorithms for lists (e.g., search and modifications)

Algorithms for trees (e.g., search , visit and queue)

Algorithms for hash tables (e.g., insertion and deletion)

Algorithms for order statistics and for disjoint sets.

Algorithms for graphs (e.g., visit and connected components)

Analysis of algorithms correctness

Bibliography

T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein. Introduction to algorithms, MIT Press, 2011.

C. Demestrescu, I. Finocchi, G. F. Italiano. Algoritmi e strutture dati, McGraw Hill, 2008.

P. Crescenzi, G. Gambosi, R. Grossi. Strutture di Dati e Algoritmi, Pearson, 2006

Teaching methods

Lessons.

Assessment methods and criteria

The final exam consists of a written test that regards the theoretical and practical parts of the course.

Other information

- - -