## 20410336 - IN110 - Algorithms and Data Structure

Provide a good knowledge in the design of algorithms for the solution of problems and in algorithm coding with a programming language (C language). Introduce the student to some of the fundamental concepts of discrete mathematics (with brief overview on graph theory) and in particular to the basic elements of discrete optimization (optimization algorithms on graphs, visit of graph, shortest paths, spanning trees).

Curriculum

teacher profile | teaching materials

Programme

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".

Core Documentation

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.

Reference Bibliography

A.V. Aho, J.E. Hopcroft, J.D. Ullman, "Data structures and algorithms", Addison-Wesley. B.W. Kernighan, D.M. Ritchie, "C Language", second edition, Pearson - Prentice Hall, 1988. B.W. Kernighan, R. Pike, "The practice of programming", Addison-Wesley, 1999.

Type of delivery of the course

Theory lessons in the classroom and programming exercises in the computer lab. The lessons are recorded on the Microsoft Teams platform and can also be used remotely. Lessons are held in Italian.

Attendance

Lessons take place in the classroom. C programming exercises take place in the computer laboratory. Attendance of in-person lessons and exercises is strongly recommended for all students.

Type of evaluation

Written exam of programming in C language; oral exam on theoretical topics. "In itinere" evaluation tests are foreseen with written exercises of algorithm design and programming in C language which, if passed, exempt the student from the written exam.

teacher profile | teaching materials

Programme

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".

Core Documentation

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.

Reference Bibliography

A.V. Aho, J.E. Hopcroft, J.D. Ullman, "Data structures and algorithms", Addison-Wesley. B.W. Kernighan, D.M. Ritchie, "C Language", second edition, Pearson - Prentice Hall, 1988. B.W. Kernighan, R. Pike, "The practice of programming", Addison-Wesley, 1999.

Type of delivery of the course

Theory lessons in the classroom and programming exercises in the computer lab. The lessons are recorded on the Microsoft Teams platform and can also be used remotely. Lessons are held in Italian.

Attendance

Lessons take place in the classroom. C programming exercises take place in the computer laboratory. Attendance of in-person lessons and exercises is strongly recommended for all students.

Type of evaluation

Written exam of programming in C language; oral exam on theoretical topics. "In itinere" evaluation tests are foreseen with written exercises of algorithm design and programming in C language which, if passed, exempt the student from the written exam.