ALGORITHMS AND DATA STRUCTURES - PART 1

Academic year 2018/2019 Syllabus of previous years
Official course title ALGORITMI E STRUTTURE DATI - MOD.1
Course code CT0371 (AF:248803 AR:136463)
Modality On campus classes
ECTS credits 6 out of 12 of ALGORITHMS AND DATA STRUCTURES
Degree level Bachelor's Degree Programme
Educational sector code INF/01
Period Annual
Course year 2
Where VENEZIA
Moodle Go to Moodle page
Contribution of the course to the overall degree programme goals
The course is one of the fundamental courses of the Bachelor's Degree in Informatics and provides an introduction to algorithms, namely the formalization of problems, the identification of computational solutions, and the analysis of such solutions, from the point of view of correctness and efficiency in the use of resources. Furthermore, fundamental data structures and basic techniques for the design and analysis of the algorithms will be presented.
Expected learning outcomes
Knowledge and understanding:
- knowledge and understanding of the fundamental algorithms and data structures;
- understanding and evaluation of the complexity of computational problems and the ability to select appropriate methods for modeling and solving them;

Ability to apply knowledge and understanding:
- logical-deductive and problem-solving skills;
- ability to formalize and implement solutions for real problems and identification of appropriate solution patterns.

Evaluation skills
- being able to formulate and argue solutions, also developing a critical approach to the evaluation of alternative solutions.
Pre-requirements
Knowledge of the basic concepts of discrete mathematics and calculus.
Contents
Algorithms, computation models and analysis techniques: Informal introduction to algorithms. Computation models. Asymptotic notation. Recurrences.

Fundamental techniques for algorithm design: Divide-and-conquer. Dynamic programming. Greedy algorithms.

Graph algorithms: Graph representations. Breadth-first and depth-first search. Minimum spanning trees (Kruskal, Prim). Shortest paths (Dijkstra, Bellman-Ford, Floyd-Warshall).

NP-complete problems: complexity classes P and NP. Polynomial reducibility and NP-completeness. Examples of NP-complete problems.
Referral texts
T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein.
Introduction to algorithms (3rd Edition), MIT Press, 2009.

C. Demetrescu, I. Finocchi, G. F. Italiano.
Algoritmi e strutture dati (seconda edizione), McGraw-Hill, 2008.
Assessment methods
The exam consists in a written test and an oral test. The written test lasts 3 hours and it is divided into two parts. The first part consists of 3 questions to be solved in 30 minutes. These questions require a quick answer on topics covered in class and they are aimed at testing the acquisition of the basic concepts of the course. The second part consists of four exercises, some of which are intended to assess the skills acquired in solving computational problems by designing efficient algorithms, while others aim at testing the acquisition of knowledge provided by the lessons. The written test may be replaced by successful completion of two intermediate examinations, each lasting two hours and consisting of 3 exercises, with the same types of exercises of the second part of the written test.
During the written test is not allowed the use of books, notes, electronic media.

During the oral exam, the student must demonstrate to manage the topics presented in class and be able to expose them in a formal way.

The students are assigned exercises in C. The purpose is to implement data structures, design techniques and algorithms presented in class and do exercise on the calculation of complexity. Making such exercises allows to get a bonus.
Teaching methods
Chalk lectures and slides (when needed).
Teaching language
Italian
Type of exam
written and oral
Definitive programme.
Last update of the programme
02/05/2018