B4913 - ALGORITMI E STRUTTURE DATI (9 CFU)

Learning outcomes

Students will learn basic concepts about the fundamental algorithms (divide and conquer, dynamic programming, greedy method, backtracking, local search) to solve well knwon computational problems, and the basic data structures and abstract data types (lists, queues, trees, graphs, etc.), as well as techniques (asymptotic notation, recurrences) for evaluation of computational complexity of algorithms (and computation complexity classes P, NP, NP-hard) and space complexity of algorithms execution (memory space). The course will offer the illustration of trade-offs and sinergies between algorithms and data structures, and a training on methodologies to realize the design of efficient algorithms and correspondingly appropriate data structures to solve both generalized and specific instances of computational problems, under pre-defined assumptions and requirements

Course contents

Basic data structures (List, Queue, Stack, Trees...)

Computational Complexity

Searching and Sorting Algorithms

Sets, Dictionaries, Trees, Binary search, RB trees

Heaps, Hash tables, Priority queues, Union-Find data structures

Algorithmic techniques: divide et impera, greedy algorithms, dynamic programming,

Graphs and graph algorithms: depth-first visit and breadth-first visit,

Elementary graph algorithms, Minimum Spanning Tree, shortest paths algorithms

Introduction to NP-completeness theory

Readings/Bibliography

Official text:

Alan A. Bertossi, A. Montresor, Algoritmi e Strutture di Dati [https://www.cittastudi.it/catalogo/scienze/algoritmi-e-strutture-di-dati-1802], CittàStudi 2014, ISBN: 9788825173956

 

Recommended readings:

Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano, Algoritmi e strutture dati 2/ed, McGraw-Hill, 2008, ISBN: 978 88 386 64687

Camil Demetrescu, Umberto Ferraro Petrillo, Irene Finocchi, Giuseppe F. Italiano, Progetto di Algoritmi e Strutture Dati in Java, McGraw-Hill, 2007, ISBN: 9788838663741

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduzione agli algoritmi e strutture dati 2/ed, McGraw-Hill, 2005, ISBN: 9788838662515

Teaching methods

Lectures and interactive exercises

Assessment methods

Six exam sessions are scheduled each academic year: three in the summer session (June/July); one in the fall session (September); and two in the winter session (January/February).

Assessment is conducted through a project and an oral exam. The project aims to assess the student's ability to solve computational problems through the design and implementation of efficient algorithms and to verify the acquisition of the knowledge required by the course syllabus.

Projects must be graded at least sufficient (i.e., a score ≥ 18/30) to be considered for the exam. The oral exam, also graded out of 30, includes a discussion of the submitted projects, during which questions may be asked to assess the student's acquisition of the knowledge required by the entire course syllabus.

The final grade, expressed out of 30, takes into account the grades obtained in the projects and the oral exam.

Teaching tools

The lectures utilize overhead slides projected from a laptop computer together with a white board, scientific papers made available to student, etc. The material presented during lectures will be made available in electronic format for downloading from the Course web site.

Office hours

See the website of Jocelyne Elias

See the website of Davide Rossi