Teaching code

4S02751

Academic staff

Ugo Solitro, Matteo Mantovani

Coordinator

Ugo Solitro

Credits

12

Language

Italian

Scientific Disciplinary Sector (SSD)

INF/01 - INFORMATICS

Period

Semester 1, Semester 2

Lessons timetable Moodle Seminars 0

Learning objectives

This course proposes providing the fundamentals skills in order to analyze and resolve problems by means of developing programs. The general objectives of this module are - the knowledge of the principles of programming and of programming languages, - the mastery of fundamental techniques for analyzing problems and developing their algorithmic solutions, - the introduction to the methods for the evaluation of correctness and efficiency of algorithms. In the laboratory, we will practice the above principles by means of a programming activity.

Prerequisites and basic notions

Knowledge and mathematical and scientific skills provided by the upper secondary school.
In particular:
- Sets, functions, relations and graphs.
- Numerical sets and their fundamental properties.
- Plane geometry and Cartesian representation of geometric elements.
- Representation of data, relations and functions.

Program

INTRODUCTION

- Problems and Solutions.
- Models of Computations: abstract machine, compiler and interpreter.
- Programming languages: formal languages, compiler, interpreter.
- Laboratory: introduction to linux and to the developing environment.

PART I - Problems, algorithms and programs.

- Imperative programming
- Elementary of programming: basic instructions and development of simple programs; variables, expressions and assignment.
- Data types. The general concept of data type: characterisation and data representation. Abstract Data Types.
- Primitive data types: characterisation, use and related problems.
- Structured data types: array, record, file, pointer, string and other data structures.
- Program structure. Fundamental instructions. Sub-programs: structure, parameters and visibility. Recursion.
- Object Oriented Programming.
- Basics of objects: classes, objects, attributes, constructors, modifiers.
- Advanced data structures: representation of sequences, vector and matrices; inductive and dynamic data structures; introduction to lists, trees and graphs.

PART II - Analysis of Algorithms

- Correctness: termination, logic properties; methods for the correctness verification.
- Efficiency of algorithms.
- Introduction to the complexity. Performance of algorithms. Evaluation of efficiency. Computational costs.
- Asymptotic estimation of the complexity in time and space. The worst and medium case.
- Amortised analysis.
- Study of fundamental examples.
- Sequences: static and dynamic implementation and algorithms.
- Research and Sorting Algorithms: basic search, binary search, insertion and selection sort, merge sort, quick sort.
- Matrices and Vectors: implementation, operations and algorithms.
- Dynamic sequences: abstract definition and implementation; basic operations.
- Trees. Abstract definition and implementation. Basic operation. Binary research trees.
- Introduction to algorithms on graphs.

PRACTICAL PART.

During the practical activities that take place in the Laboratory, all the techniques necessary to apply the topics developed in theory lessons are introduced through the use of programming languages. The principles of imperative programming with the Python language are introduced and the fundamental aspects of object programming with the Java language are explored.
The primary objective of the Laboratory activity is the construction of the solution of a problem through the use of a specific programming language. We address the steps that starting from the informal description of the problem lead to its resolution through the characterisation of the problem, the design of the solution and its coding.
Particular attention is paid to the use of methods and techniques that improve the legibility, maintainability and reuse of the code.

Bibliography

Didactic methods

The teaching consists of lessons and exercises in the classroom and in the laboratory with the possible use of a computer.
Some learning activities have to be carried out as homeworks.
Additional resources will be available in the reserved area of the course.

Learning assessment procedures

The final exam consists of an oral exam: in order to be admitted to the final exam, the student must pass a preliminary written test.
The written test can be partially replaced by ongoing tests and activities.
The assessment methods could change according to the evolution of the general health situation and the academic rules.

Evaluation criteria

The exams are aimed at verifying:
- the general knowledge of the fundamental constructs of imperative and object-oriented programming;
- the ability to use a programming language effectively and correctly;
- the ability to manage the problem solving process: description and rigorous characterization of problems, design of the data representation, design and development of the solution code, analysis of the efficiency and correctness of the solution.

Criteria for the composition of the final grade

The final grade is obtained as the average of the assessments of the three scheduled tests: written, practical and oral.
NOTE: to pass the final exam it is necessary to obtain a positive evaluation - at least 60% of the score - in each of the three tests indicated.

Exam language

Italiano