ALGORITHMS AND DATA STRUCTURES - PART 1

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.

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.

Knowledge of the basic concepts of discrete mathematics and calculus.

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.

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.

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. To take the second mid-term test it is necessary to have passed the first mid-term test, and the second mid-term test can only be taken at the first session of the summer session.

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.

Chalk lectures and slides (when needed).

Italian

written and oral