11929 - Algorithms and Data Structures

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...) Asymptotic Algorithmic Complexity
Algorithms for Sorting and Searching 
Lower bound for the complexity of comparison-based sorting algorithms
Sorting in linear time  
Selection algorithms (QuickSelect)
Binary search trees, AVL trees
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

Readings/Bibliography

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

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

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

Assessment methods

The assessment consists in a final written examination, lasting 3 hours. The purpose of the written exam is to check the practical ability to design correct and efficient algorithms to solve computational problems, and to verify that the expected theoretical knowledge has been acquired. 

The written examination may be replaced by the development of projects that, once positively assessed, (must obtain an assessment ≥ 18/30), will be discussed with the teachers.

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 Gianluigi Zavattaro