Università Roma Tre

1. Problems and algorithms
Introduction to the characteristics of the computer and to the programmer / executor relationship; duties and skills of the programmer; main characteristics and skills of the exporter, basic operations (logic, arithmetic and comparison). Calculating machine models: notes on the Von Neumann model and on the Turing machine.
Programming languages: imperative and declarative languages. Fundamental instructions of a generic procedural programming language. Algorithms and programs; flowcharts. Structured programming rules, notes on the Jacopini-Böhm theorem; top-down approach to solving a problem.

2. The C language
Organization of the memory of a computer, addresses, words, pointers. Binary coding. Data types, data structures (arrays, matrices, stacks, queues, priority queues, lists, trees, graphs). Machine language, high-level languages; compilers and interpreters, compilation and execution of a C program in UNIX / Linux environment. The C language: aims and main characteristics.
The structure of a C program, the inclusion of headers, declaration of variables; libraries. Elementary data types in C language: integers, floating point, double, char. Arithmetic operators, evaluation of logical expressions and logical connectors. Pointers; arithmetic on pointers. Arrays and matrices and their representation in memory. Complex data structures: lists, trees, graphs; the "struct" instruction. Assignment operator, arithmetic operators in C in extended and compact form. Control structures: “if ... else ...”, “while ...”, “do ... while”, “for ...”.
Functions: library functions and user-defined functions. Passing parameters by value and by address to functions. Recursive functions. Input / output functions: "printf", "scanf", "fprintf", "fscanf"; memory management functions: "malloc", "free", "sizeof"; management of lists of records linked by pointers.

3. Sorting algorithms
Elementary sorting algorithms: Insertion sort, Selection sort, Bubble sort; the "divide and conquer" approach, the Quick sort algorithm. LIFO (Last In First Out) type structures, stack; FIFO (First In First Out) structures, queues; priority queues, heaps. Optimal algorithms for sorting: Heap sort, Merge sort.
Complexity of an algorithm in the worst case, the notation "Big O", analysis of the complexity of the sorting algorithms.

4. Elementary algorithms on graphs
Main definitions: graph, directed graph; subgraph, induced subgraph; path, simple path, connected graph, strongly connected graph, complete graph, clique, cycle, acyclic graph; trees, forests, spanning tree of a graph. Data structures for the representation of graphs using a computer: adjacency lists and adjacency matrices. Algorithms for visiting a graph: amplitude visit (BFS), depth visit (DFS), topological ordering of an acyclic oriented graph. Minimum cost path problems on a graph, Dijkstra's algorithm.
Complexity analysis of the presented algorithms. Notes on the classes of P, NP, NP-complete problems. The problem "P = NP".

T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, "Introduzione agli algoritmi", McGraw–Hill (3rd Edition)
A. Bellini, A. Guidi, Linguaggio C - Guida alla programmazione, McGraw-Hill (5th Edition)
M. Liverani, "Programmare in C", Esculapio (2nd edition)

Lecture notes and other teaching material in Italian provided by the teacher and made available on the course website (http://www.mat.uniroma3.it/users/liverani/IN110) and on the Microsoft Teams platform