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
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 "O large", 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".
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
Programme
1. Problems and algorithmsIntroduction 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 "O large", 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.Type of evaluation
Written exam of programming in C language; oral exam on theoretical topics. teacher profile teaching materials
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 "O large", 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".
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
Programme
1. Problems and algorithmsIntroduction 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 "O large", 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.Type of evaluation
Written exam of programming in C language; oral exam on theoretical topics. teacher profile teaching materials
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 "O large", 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".
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
Programme
1. Problems and algorithmsIntroduction 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 "O large", 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.Type of evaluation
Written exam of programming in C language; oral exam on theoretical topics. teacher profile teaching materials
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 "O large", 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".
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
Programme
1. Problems and algorithmsIntroduction 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 "O large", 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.Type of evaluation
Written exam of programming in C language; oral exam on theoretical topics.