Computer Science

0. Introduction to the Course 1. cable networks 1.1. The Routing problem, i.e., the minimum cost shortest path 1.2. The layout of interconnection networks, i.e., the orthogonal grid graph drawing 1.3. The problem of infecting a network with a worm, i.e., the minimum vertex cover problem 1.4. The problem of minimizing a Boolean circuit, i.e., the minimum set covering problem 2. wireless ad hoc networks 2.1. The frequency assignment problem, i.e., a graph coloring problem 2.2. The minimum energy broadcast problem, i.e,. the minimum spanning tree problem 2.3. The data mule scheduling problem, i.e., the travelling salesman problem 2.4. The Data Collection in ad-hoc networks, i.e., the connected Dominating Set Problem 3. mobile sensor networks 3.1. The centralized deployment of a mobile sensor network, i.e., the minimum cost perfect matching in bipartite graphs 3.2. Self-deployment of a mobile sensor network, i.e., the Voronoi Diagram 3.3. Monitoring by UAVs, i.e., the multiple TSP with constraints

In order to profitably attend the Network Algorithms teaching lessons, the fundamentals of Algorithms, of data structures, and of computational complexity are essential, which will be used as an already consolidated basis. This knowledge is usually provided in two courses of the bachelor's degree in Computer Science (at least 18 credits). Students aware that they do not possess these prerequisites are strongly encouraged to obtain them before attending class.

Course topics are mostly from recent research, for which there is no textbook, but rather a number of articles which can be downloaded from the course page. For further details, see here: https://twiki.di.uniroma1.it/twiki/view/Algoreti/ProgrammaDelCorso

Remote teaching mode. Beside the recorded lectures, there is a support activity by the teacher and a "tutoring" activity in which exercises are proposed to students, in agreement with them about the topics. Attending lectures is not compulsory.

attending lessons is not compulsory but strongly encouraged.

For the students attending the lessons, the Exam Procedure is composed of two compulsory oral parts. The first part consists of a short lesson (about half an hour), taught by the student, on a research paper assigned by the teacher. During the final exam, the whole chapter, including the topic of the lesson, will be skipped. The aim of this first part of the exam is to allow students to engage with a scientific text, learn to understand it, summarize it, and explain it to others. The second part consists of an oral exam on all the remaining topics. The aim of this second test is to enable students to acquire a unified and organic understanding of the topic, to be able to make connections, and to clearly report on a familiar topic. Students can divide this latter oral exam into two mid-semester sub-exams; they can freely decide how many chapters they want to study for the first mid-semester sub-exam, which will be held approximately in mid-November (during the week without teaching, when decided). It is worth mentioning that, as far as the chapters are organized, this exam is not recommended to students who, for any reason, cannot attend the lessons. Nevertheless, the students that anyway wish to take this exam will have to take a unique oral exam, including all topics. International students will take the exam using the same methods. To pass the exam, students must achieve a grade of at least 18/30. Students must demonstrate sufficient knowledge of the topics covered in all sections of the program. To achieve a grade of 30/30 with honors, students must demonstrate excellent knowledge of all the topics covered in the course and be able to connect them in a logical and coherent manner.

The teaching format is mostly traditional (lectures by the teacher). In some lessons, students will present a topic on a previously studied paper (students' lessons). Attending lectures is not compulsory but highly recommended.

0. Introduction to the Course 1. cable networks 1.1. The Routing problem, i.e., the minimum cost shortest path 1.2. The layout of interconnection networks, i.e., the orthogonal grid graph drawing 1.3. The problem of infecting a network with a worm, i.e., the minimum vertex cover problem 1.4. The problem of minimizing a Boolean circuit, i.e., the minimum set covering problem 2. wireless ad hoc networks 2.1. The frequency assignment problem, i.e., a graph coloring problem 2.2. The minimum energy broadcast problem, i.e,. the minimum spanning tree problem 2.3. The data mule scheduling problem, i.e., the travelling salesman problem 2.4. The Data Collection in ad-hoc networks, i.e., the connected Dominating Set Problem 3. mobile sensor networks 3.1. The centralized deployment of a mobile sensor network, i.e., the minimum cost perfect matching in bipartite graphs 3.2. Self-deployment of a mobile sensor network, i.e., the Voronoi Diagram 3.3. Monitoring by UAVs, i.e., the multiple TSP with constraints

In order to profitably attend the Network Algorithms teaching lessons, the fundamentals of Algorithms, of data structures, and of computational complexity are essential, which will be used as an already consolidated basis. This knowledge is usually provided in two courses of the bachelor's degree in Computer Science (at least 18 credits). Students aware that they do not possess these prerequisites are strongly encouraged to obtain them before attending class.

Course topics are mostly from recent research, for which there is no textbook, but rather a number of articles which can be downloaded from the course page. For further details, see here: https://twiki.di.uniroma1.it/twiki/view/Algoreti/ProgrammaDelCorso

Remote teaching mode. Beside the recorded lectures, there is a support activity by the teacher and a "tutoring" activity in which exercises are proposed to students, in agreement with them about the topics. Attending lectures is not compulsory.

attending lessons is not compulsory but strongly encouraged.

For the students attending the lessons, the Exam Procedure is composed of two compulsory oral parts. The first part consists of a short lesson (about half an hour), taught by the student, on a research paper assigned by the teacher. During the final exam, the whole chapter, including the topic of the lesson, will be skipped. The aim of this first part of the exam is to allow students to engage with a scientific text, learn to understand it, summarize it, and explain it to others. The second part consists of an oral exam on all the remaining topics. The aim of this second test is to enable students to acquire a unified and organic understanding of the topic, to be able to make connections, and to clearly report on a familiar topic. Students can divide this latter oral exam into two mid-semester sub-exams; they can freely decide how many chapters they want to study for the first mid-semester sub-exam, which will be held approximately in mid-November (during the week without teaching, when decided). It is worth mentioning that, as far as the chapters are organized, this exam is not recommended to students who, for any reason, cannot attend the lessons. Nevertheless, the students that anyway wish to take this exam will have to take a unique oral exam, including all topics. International students will take the exam using the same methods. To pass the exam, students must achieve a grade of at least 18/30. Students must demonstrate sufficient knowledge of the topics covered in all sections of the program. To achieve a grade of 30/30 with honors, students must demonstrate excellent knowledge of all the topics covered in the course and be able to connect them in a logical and coherent manner.

The teaching format is mostly traditional (lectures by the teacher). In some lessons, students will present a topic on a previously studied paper (students' lessons). Attending lectures is not compulsory but highly recommended.