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
scheda docente
materiale didattico
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", quinta edizione, McGraw-Hill, 2013 (or and other C programming manual)
M. Liverani, "Programmare in C", Esculapio (terza edizione)
Lecture notes and other teaching material in Italian provided by the teacher and made available on the course website (https://www.mat.uniroma3.it/users/liverani/IN110) and on the Microsoft Teams platform
Programma
"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""."
Testi Adottati
T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, "Introduction to algorithms", The MIT Press (Fourth edition)A. Bellini, A. Guidi, "Linguaggio C - Guida alla programmazione", quinta edizione, McGraw-Hill, 2013 (or and other C programming manual)
M. Liverani, "Programmare in C", Esculapio (terza edizione)
Lecture notes and other teaching material in Italian provided by the teacher and made available on the course website (https://www.mat.uniroma3.it/users/liverani/IN110) and on the Microsoft Teams platform
Bibliografia Di Riferimento
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.Modalità Frequenza
Attendance at classroom lectures (twice a week) and computer lab exercises (once a week) is recommended. Weekly meetings with student tutors will also be held to help students complete additional exercises under guidance.Modalità Valutazione
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.
scheda docente
materiale didattico
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", quinta edizione, McGraw-Hill, 2013 (or and other C programming manual)
M. Liverani, "Programmare in C", Esculapio (terza edizione)
Lecture notes and other teaching material in Italian provided by the teacher and made available on the course website (https://www.mat.uniroma3.it/users/liverani/IN110) and on the Microsoft Teams platform
Programma
"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""."
Testi Adottati
T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, "Introduction to algorithms", The MIT Press (Fourth edition)A. Bellini, A. Guidi, "Linguaggio C - Guida alla programmazione", quinta edizione, McGraw-Hill, 2013 (or and other C programming manual)
M. Liverani, "Programmare in C", Esculapio (terza edizione)
Lecture notes and other teaching material in Italian provided by the teacher and made available on the course website (https://www.mat.uniroma3.it/users/liverani/IN110) and on the Microsoft Teams platform
Bibliografia Di Riferimento
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.Modalità Frequenza
Attendance at classroom lectures (twice a week) and computer lab exercises (once a week) is recommended. Weekly meetings with student tutors will also be held to help students complete additional exercises under guidance.Modalità Valutazione
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.