Network Algorithms

Algoritmi per le Reti

A.y./A.A. 2025/26

Prof. Tiziana Calamoneri

Notices/Avvisi

Oct. 15, 2025: Mid-term exam moved to the afternoon (13,30-16,00) in order to avoid overlapping with the mid-term exam of Autonomous Networking

Oct. 8, 2025: Some important dates:

- Classes will be suspended in the week Oct.30-Nov.5, 2025

- On October 29 we will have a double lesson: 10-13 and 14-16

- On November 5, starting from 9,30 in G50 room, Mid-term exam

- November 16 is the deadline to communicate by email the paper chosen for the students’ lesson.

During the algorithm courses you have already attended, you have been told that algorithms in general, and graph algorithms in particular, are important because they are able to model the solution of a number of real-life problems: designing a good algorithm often turns out to have a good solution for the initial problem. Nevertheless, probably nobody detailed to you what these real-life problems are.

During this course, I will show you many real-life problems arising from using communication networks (cable or wireless networks, fixed or mobile networks), and, for each of them, we will discuss together how a problem can be modeled as a classical graph problem and solved by means of a graph algorithm, proposing sometimes more than one solution. In the first part of the course, I will propose some classical problems (together with their algorithmic solutions). In the second part of the course, I will deal with some advanced problems, especially related to wireless, ad hoc, and sensor networks. Of course, these latter problems are particularly feasible to be studied in a master's thesis, with good possibilities to find some new results.

It is worth noting that the approach of the course is algorithmic, so a special emphasis is placed on the method used to find the optimal solution or, at least, the best possible one. This also means that you should have knowledge of non-trivial algorithms, data structures, and the foundation of computational complexity, in order to attend this course with profit.

Nei corsi di algoritmi che avete seguito vi è stato certamente detto che gli algoritmi in generale, e gli algoritmi su grafi in particolare, sono importanti perché possono modellare tanti problemi della vita reale, ed avere un buon algoritmo per un problema su grafi significa spesso avere una buona soluzione per il relativo problema reale. Ma di quali siano in concreto questi problemi reali non si è quasi mai parlato. Ebbene, quello che invece cercherò di fare in questo corso è mostrarvi molti problemi "reali" che nascono dall'utilizzo di reti di comunicazione di vario tipo (cablate e senza fili, fisse e mobili) e, per ciascuno di essi, discuteremo come sia possibile modellarlo tramite un problema algoritmico classico e proporre quindi una o più soluzioni. Nella prima parte del corso, vi proporrò delle problematiche (e rispettive soluzioni algoritmiche) classiche, e quindi legate essenzialmente alle reti cablate. Nella seconda parte, invece, tratterò di argomenti di ricerca attuale, specie nel campo delle reti wireless ad hoc e delle reti di sensori. In particolare questi ultimi argomenti, come è ovvio, saranno particolarmente adatti a diventare argomenti di tesi di ampio respiro e con buone prospettive di trovare dei nuovi risultati.

L'approccio del corso sarà comunque algoritmico, e quindi si porrà particolare accento sul metodo con cui sia possibile trovare la soluzione ottima o, almeno, la più efficiente possibile. Ciò significa anche che, per seguire con profitto questo corso, dovreste conoscere gli algoritmi e le strutture dati non banali, e i fondamenti della complessità computazionale.

Timetable/Orario 2025/26 I semest.

Office Hours/Ricevimento A.A. 2025/26 I semester

Next meetings/Prossimi appuntamenti: *5 Nov 2025 - Mid term exam

• • 13.30 in room G50
• 16 Sep 2025 - Oral exam
  • (a.y. 24/25) in the Teacher's room at 10.00 am
• 26 Jun 2025 - Oral exam
  • in the Teacher's room at 11.30 am

Exam Procedure/Modalita' d'Esame

Program and Textbook/Programma del Corso e libri di testo

Lesson Diary/Diario delle Lezioni

Lesson Slides/Slides delle Lezioni

Student Lessons' Schedule/Programma Lezioni degli Studenti