Mathematics

IVANO SALVO
ADOLFO PIPERNO

General objectives

Acquire basic knowledge on the design of basic algorithms, iterative and recursive algorithms, and the computation of their computational efficiency.

Specific objectives

Knowledge and understanding:
At the end of the course students will know the basic methodologies for the design and analysis of iterative and recursive algorithms, the main data structures, some ways to explore such structures, the main sorting algorithms and the most basic implementations of the dictionaries. They will have a good knowledge of the C language, including advanced aspects such as dynamic memory allocation, pointer arithmetic and separate program compilation.

Apply knowledge and understanding:
At the end of the course students will have become familiar with the main basic data structures, in particular those implementing dictionaries. They will be able to explain the algorithms and analyze their time complexity, highlighting how their performances depend on the used data structure. They will be able to design new data structures and related algorithms, on the basis of the existing ones; they will be able to explain the main sorting algorithms, illustrating the underlying design strategies and their time complexity analysis; they will be able to compare the asymptotic behavior of the execution times of the studied algorithms, to design recursive solutions to problems and to analyze their asymptotic time complexity. Finally, they will be able to implement the learned algorithms and data structures in the C language, with attention also to the correctness, clarity and concrete efficiency of the programs.


Critical and judgmental skills:
Students will be able to analyze the quality of an algorithm and related data structures, both from the effective resolution of the problem and from the time complexity point of views.

Communication skills:
Students will acquire the ability to expose their knowledge in a clear and organized way, which will be verified both through the written tests and during the oral examination.
Students will be able to express an algorithmic idea rigorously both at high level, through the use of the pseudocode, and in the C language.

Learning ability:
Once the cycle of studies is completed, the acquired knowledge will allow students to face the study of algorithmic techniques, of more advanced data structures and of advanced programming methodologies within a master's degree course.

Knowledge and understanding: basic algorithm on arrays, searching and sorting algorithms, data structures, and graph algorithms.
Applying knowledge and understanding: to apply algorithms to specific problems, to analyse solutions in order to improve them.
Making judgements: quick understanding of computational complexity of a problem;
Communication skills: give abstract as well synthetic descriptions (but not ambiguous) of an algorithmic solution of a problem
Learning skills: learning easily new solutions to specific problems, stemming from general techniques studied in the course:

Basic notions of Programming.

General part (60 hours):
Description and design of efficient algorithms: Introduction to the concepts of algorithm, data structure, efficiency, computational complexity. Asymptotic notation. Introduction to recursion. The problem of sorting. Basic data structures (arrays, lists, stacks, queues, priority queues, trees). Dictionaries. Graphs.

Part on the C language (24 hours):
C language: Principles of good programming (structured programming, development of correct codes following a top-down methodology by structuring code with use of functions). Recall of elementary notions of the C language: iterative constructs and functions, vectors and structures. Recursion in C. Pointers and dynamic memory allocation. Lists and binary trees.

Reference text:
T. H. Cormen, Charles E. Leiserson, Ronald L. Rivest: Introduction to algorithms, The MIT Press

It will be the teachers' responsibility to distribute didactic material, related to the lessons and exercises of the general part (in the form of teacher's notes) and to the C language (in the form of handouts and sample programs written in C language).

J. Kleimberg, E. Tardos: "Algorithm Design", Pearson, 2006.
E. W. Dijkstra: "A Discipline of Programming", Prentice Hall, 1976.
J. Bentley: "Programming Pearls" (1986) and "More Programming Pearls" (1988), Addison Wesley.

Lessons are traditional with slides.
Blended lessons will be available depending on pandemic evolution.

Following lectures is highly recommended.

The exam aims at evaluating what students have learned through a *written test* (consisting in solving problems of the same type as those carried out in the exercises), homeworks (consisting in writing and running C programs of varying difficulty) and an *oral exam* (consisting in the discussion of the most relevant topics illustrated in the course). The written test will last about two hours and can be replaced by intermediate tests (about 1 hour each).
To pass the exam, students need to achieve a grade of not less than 18/30. Students must demonstrate that they have acquired sufficient knowledge of the topics of both parts of the program. To achieve a score of 30/30 cum laude, students must instead demonstrate that they have acquired excellent knowledge of all the topics covered during the course and be able to link them in a logical and coherent manner.

To determine complexity of a given algorithm.
Design algorithms on arrays, lists, trees and graphs.
Apply typical techniques of algorithm design.

• Introduzione al pensiero computazionale


• Problemi di ricerca, ordinamento e affini


• Introduzione alle Strtutture Dati: Liste, Pile, Alberi, ABR, Heap


• Algoritmi base su grafi