ALGORITMI E STRUTTURE DATI E LABORATORIO
Carla Piazza
Gabriele Puppis
Francesco Fabiano
OBIETTIVI FORMATIVI
Index:
Basics
The role of algorithms
Algorithm Design
Correctness
Computational Complexity
Basic Data Structures and Algorithms
Arrays, Heaps, Lists, Stacks, Queues, Binary Trees, Hash Tables, and similars.
Algorithms for sorting, searching, insertion, deletion over basic data structures
Proofs of correctness
Computational complexity evaluations
Advanced Data Structures and Design Techniques
Balanced binary trees and search/insert/delete algorithms
B-trees and search/insert/delete algorithms
Data structures for disjoint sets
Graphs and basic graph algorithms
Minimum Spanning Trees
Shortest paths problems/algorithms
Correctness and Complexity of the above listed algorithms
ABILITIES
The student should be able to:
1.1. Knowledge and reasoning ability
Manage basic concepts of static and dynamic data structures and design of algorithms.
Know a formal language for describing algorithms.
Evaluate computational complexities.
Know the data structures and algorithms presented during the course together with their spatial and temporal complexities.
1.2 Ability of exploiting knowledge
Implement and test algorithms seen in the course exploiting the most common programming languages.
Use the data structures and the algorithms presented in the course to design new algorithms that can solve specific problems.
Prove the correctness and evaluate the computational complexities of such algorithms
SOFT SKILLS
The student should be able to:
2.1 Judgement autonomy.
Determine which data structures, algorithms and design techniques use to provide efficient solutions to a given algorithmic problem.
Choose the most computationally efficient solution.
Combine/extend existing algorithms to solve a specific problem.
Demonstrate or refute the correctness and evaluate the computational complexity of algorithms.
Select the programming language and the most suitable libraries for implementing an algorithm.
Test implementations.
2.2 Communicative skills.
Motivate, make choices in terms of data structures and algorithms for solving a given problem.
Find any additional information needed to design an efficient algorithm.
2.3 Learning ability.
Find and exploit scientific resources for the in-depth study of topics studied in the course.
Deal with new problems of algorithmic nature.
Identify new tools for developing data structures and algorithms.
CONTENUTI
TESTI DI RIFERIMENTO
2. Further useful textbooks:
1. A. Bertossi, A. Montresor. Algoritmi e Strutture Dati, 2/ed, Città Studi Edizioni, 2010.
2. C. Demetrescu, I. Finocchi, G. F. Italiano, Algoritmi e Strutture Dati, 2/ed, McGraw-Hill, 2007.
3. P. Crescenzi, G. Gambosi, R. Grossi. Strutture di Dati e Algoritmi, Addison-Wesley Pearson, 2006.
4. Aho A.V., Hopcroft J.E., Ullman J.D., Data Structures and Algorithms, Addison-Wesley, 1983.
5. Aho A.V., Hopcroft J.E., Ullman J.D., The Design and Analysis of Computer Algorithms, Addison-Wesley, 1974.