ALGORITMI E STRUTTURE DATI E LABORATORIO

Anno accademico 2020-2021

Docenti:
Carla Piazza
Gabriele Puppis
Francesco Fabiano

Anno di corso: 2

Totale crediti: 12

Tipologia: Base

Periodo didattico: Annualità

Prerequisiti. It is necessary for the student to master the contents of the courses of the I year of the bachelor degree, with particular reference to the courses of Discrete Mathematics (Elements of Mathemathics and Linear Algebra for the degree IBW), Mathematical Analysis, Programming and Lab.

Metodi didattici. The course consists of both theoretical, practical, and lab classes. The e-learning web-page of the corse contains all the useful information for the students and some additional exercises.

Modalità di verifica. The exam is both written and oral. The student has also to pass a lab test. Upon agreement with the teacher, the exam can be given in English. The written test is mainly used to assess the skills acquired in the algorithmic resolution of problems and in the formalization of such solutions. The oral part is mainly aimed at assessing both the knowledge of data structures, algorithms, and analysis techniques presented during the course and the reasoning abilities.

OBIETTIVI FORMATIVI

Specific Objectives.

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

The course is an introduction to the foundations of the theory of algorithms and data structures, as well as to the analysis of the computational complexity of programs. The course main aim is to familiarize the student with the most important issues and techniques relative to the algorithm design and project. Moreover the basic methods employed to establish the computational complexity of programs and the criteria used to choose and design data structures are introduced. 

TESTI DI RIFERIMENTO

1. Cormen T.H., Leiserson C.E., Rivest R.L, Stein C., Introduction to Algorithms, MIT Press, Third edition, 2009.

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.