11929 - Algorithms and Data Structures

Course contents

Design and analysis of algorithms. Computational complexity. Orders of growth. Recurrence equations. Sorting algorithms: SelectionSort, InsertionSort, MergeSort, QuickSort, CountingSort, RadixSort. Data structures: lists, queues, stacks . Trees. Tree visits (preorder, inorder, postorder). Binary search trees and binary balanced search trees. Dictionaries. Hash tables. Heaps: HeapSort and Priority queues. Union-find structures. Design techniques: divide-&-conquer, greedy, dynamic programming. Graphs. DFS and BFS visits. Algorithms on graphs: Minimum Spanning Tree (Prim, Kruskal), Shortest Paths (Bellman-Ford, Dijkstra, Floyd-Warshall). Complexity. The P and NP classes. NP-completeness.

There are also practical lectures in which data structures are implemented and used, and the Object-Oriented paradigm as well as some Java notions are introduced.

Readings/Bibliography

Main text:

Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
Algoritmi e strutture dati
McGraw-Hill - terza edizione. 2025.

Suggested books:

A.A. Bertossi & A. Montresor, Algoritmi e Strutture di Dati, Citta' Studi Edizioni, Torino. Terza edizione. 2014.

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
Introduzione agli algoritmi e strutture dati
McGraw-Hill - quarta edizione. 2023.

Teaching methods

The course is taught during the second semester, and it comprises theoretical lessons and practical programming laboratory lectures. First, theoretical foundations are presented. After base notions are introduced, the main data structures and computational problems are presented. Algorithms for solving such problems are designed, pointing out the design techniques employed. For each proposed algorithm, their correctness and time (and sometimes also space) computational complexity are discussed. Next, several exercises are solved. Moreover, practical design and implementation of data structures are considered in the laboratory lessons.

Assessment methods

The assessment consists in a final written examination of 2 hours preceded by an optional Java programming project to be done individually.

The written exam lasts 2 hours, during which no books, notes, calculator and electronic devices are allowed. The written exam consists of 4 questions, some of which are exercises whose purpose is to check the practical ability to design correct and efficient algorithms to solve computational problems, while other are open-answer questions whose objective is to verify that the expected theoretical knowledge has been acquired.

The Java programming project is proposed to complement the laboratory activity and it aim is to verify whether the student has acquired the ability to implement in Java algorithms described in pseudo-code, possibly exploiting aprropriate auxiliary data structures.

The project evaluation consists of a grade between 0 and 3 which will be added to the written examevaluation expressedwith a mark out of 30.

Teaching tools

Projector and computer for the laboratory activities.

Office hours

See the website of Gianluigi Zavattaro

See the website of Pietro Di Lena