# 11929 - Algorithms and Data Structures

### Course Unit Page

• Teacher Lorenzo Donatiello

• Learning modules Lorenzo Donatiello (Modulo 1)
Jocelyne Elias (Modulo 2)

• Credits 12

• SSD INF/01

• Teaching Mode Traditional lectures (Modulo 1)
Traditional lectures (Modulo 2)

• Language Italian

• Campus of Bologna

• Degree Programme First cycle degree programme (L) in Information Science for Management (cod. 8014)

• Course Timetable from Sep 21, 2021 to Dec 02, 2021

Course Timetable from Feb 22, 2022 to May 10, 2022

### SDGs

This teaching activity contributes to the achievement of the Sustainable Development Goals of the UN 2030 Agenda.

## Learning outcomes

Students will learn basic concepts about the fundamental algorithms to solve well knwon computational problems, and the basic data structures and abstract data types, as well as techniques 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, shortest paths algorithms Introduction to NP-completeness theory

Official text:
Alan A. Bertossi, A. Montresor, Algoritmi e Strutture di Dati, CittàStudi 2010, ISBN: 9788825173567

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

Classroom lecturers with projection of electronic slides,exercises, homeworks and projects.

## Assessment methods

The assessment of learning takes place through the development of a project and an oral test. The aim of the project is to verify the practical ability to design and implement correct and efficient algorithms. The evaluation of the project must be at least sufficient (ie the assessment ≥ 18/30) to be valid for the exam. The oral exam consists of a discussion of the results obtained in the project and its goal is to check the understanding of the concepts introduced in the lectures and the ability of being able to use them in concrete situations

## Teaching tools

All course material (lecture slides, exercises and other resources) will be made available on the course web page.

## Links to further information

http://www.cs.unibo.it/~donat/

## Office hours

See the website of Lorenzo Donatiello

See the website of Jocelyne Elias