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, piles; 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.

This course aims to provide students with a solid foundation in C programming, focusing on structured programming, memory management, and the implementation of data structures. Through a hands-on and lab-based approach, students will gain the opportunity to learn the fundamentals of programming and apply them directly in the development of algorithms and software solutions.

In the first part of the course, the basics of structured programming will be introduced, with special emphasis on algorithm synthesis, flowchart creation, and pseudocode writing. These core concepts will be complemented by a practical introduction to the development environment and the use of the C compiler, allowing students to execute their first programs.

Subsequently, the course will dive deeper into iterative and conditional structures, with practical examples of implementation in C. Key concepts such as arrays and dynamic memory allocation will also be covered, providing a detailed exploration of memory management in C, including Activation Records (AR) and techniques to optimise resource usage.

A central part of the course will focus on handling complex structures in C, such as structs, and the implementation of fundamental data structures. Students will learn how to design and implement stacks, queues, priority queues, linked lists, doubly linked lists, trees, and graphs, with a focus on real-world use cases and efficient algorithms.

The course will conclude with the study of sorting algorithms and graph algorithms, equipping students with the necessary skills to tackle more complex programming problems and preparing them to face advanced challenges in the field of informatics.