Lesson Diary A.y. 2024-2025

Monday, September 23, 2024 (Lessons 1-2-3):

Introduction

The Routing Problem i.e. the Least Cost Path Problem (1)

• The routing Problem
• The shortest path Problem
  • shortest paths: BFS
  • a parenthesis on the Connected Components Problem and its applications
• The least cost path Problem (1)
  • the negative cycle issue and its applications
  • least cost paths: introduction
  • Bellman-Ford algorithm

Thursday, September 26, 2024 (Lessons 4-5):

The Routing Problem i.e. the Least Cost Path Problem (2)

• The least cost path Problem (2)
  • Dijkstra algorithm
  • Floyd-Warshall algorithm
• The Routing Problem on Interconnection Topologies
  • the packet-switching model
  • the Butterfly network
  • routing on the Butterfly network: the greedy algorithm
  • The concept of blocking network, non-blocking network, and rearrangeable network

Monday, September 30, 2024 (Lessons 6-7-8):

The Routing Problem i.e. the Least Cost Path Problem (3)

• The Routing Problem on Interconnection Topologies
  • The Benes network
  • routing on the Benes network: the looping algorithm

The Problem of Laying out Interconnection Topologies i.e. the Grid Orthogonal Drawing Problem (1)

• The Thompson model
• The orthogonal grid drawing of graphs
• Layout of the complete binary tree (H-tree)
• Collinear Layout of the Complete network
• Layout of the Complete network

Thursday, October 3, 2024 (Lessons 9-10):

The Problem of Laying out Interconnection Topologies i.e. the Grid Orthogonal Drawing Problem (2)

• Relation between bisection width and layout area
• Layout of the Butterfly network
  • The Wise layout

• Layout of the Butterfly network
  • The Even & Even layout
  • comparison between the two methods
  • Optimal area layout

Monday, October 7, 2024 (Lessons 11-12-13):

The Problem of Laying out Interconnection Topologies i.e. the Grid Orthogonal Drawing Problem (3)

• Layout of the Hypercube network
  • Collinear layout
  • general layout
• The 3D layout problem

The problem of worm propagation/prevention i.e. the Minimum Vertex Covering Problem (1)

• The problem
  • worms
  • damages caused by worms
• Model of the problem on graphs: minimum vertex cover
  • Definition
  • ILP model
  • a 2-approximation algorithm
  • independent set and maximum matching in relation to vertex cover
  • another approximation algorithm

Thursday, October 10, 2024: NO LESSON

Monday October 14, 2024 (Lessons 14-15-16):

The problem of worm propagation/prevention i.e. the Minimum Vertex Covering Problem (2)

• Model of the problem on graphs: minimum vertex cover * Konig-Egevary theorem (without proof)
• A related problem: eternal vertex problem

A Frequency assignment problem i.e. the L(h,k)-Labeling Problem (1)

• Introduction to the frequency assignment problems
• Direct and hidden collisions, interference graph
• Introduction to the frequency assignment problems
• Direct and hidden collisions, interference graph
• L(h,k)-labeling and minimum span (1)
  • The special case h=k in relation to the square of a graph
  • Properties of the L(h,k)-labeling and their proofs

Thursday, October 17, 2024 (Lessons 17-18):

A Frequency assignment problem i.e. the L(h,k)-Labeling Problem (2)

• L(h,k)-labeling and minimum span (2)
  • Proof of NP-completeness for diameter 2 graphs
  • Lower bound of Delta+1 on lambda
  • Example: a graph requiring lambda=Delta squared - Delta
  • Upper bound of Delta squared + 2 Delta
  • Griggs and Yeh's conjecture
  • Exact results: cliques
  • Exact results: stars
  • Exact results: trees
  • Exact results: paths
  • Exact results: cycles
  • Exact results: grids
  • Approximate results: outerplanar graphs

Monday, October 21, 2024 (Lessons 19-20-21):

A Frequency assignment problem i.e. the L(h,k)-Labeling Problem (3)

• Variations of the problem
  • oriented L(2,1)-labeling
  • L(h1, ..., hk)-labeling
  • backbone coloring
  • multiple L(h,k)-labeling
• a parenthesis on the 4-color theorem

The minimum energy broadcast i.e. the minimum spanning tree (1)

• The Min Broadcast problem
• NP-completeness and inapproximability results (reduction from Min Set Cover)
• Relation between Min Broadcast and Min Spanning Tree (MST)

Thursday, October 24, 2024 (Lessons 22-23):

The minimum energy broadcast i.e. the minimum spanning tree (2)

• The MST problem
  • Kruskal algorithm
  • Prim algorithm
  • Boruvka algorithm
• The Min Broadcast problem
  • MST heuristics
  • SPT heuristics
  • BAIP heuristics
  • approximation ratio for MST

Monday, October 28, 2024 (Lessons 24-25-26):

FIRST MID-TERM EXAM

Thursday, October 31, 2024 (Lessons 27-28):

Avi Wigderson's seminar. All further details, including the streaming link, can be found at https://www.mat.uniroma2.it/~rds/events.php

Monday, November 4, 2024 (Lessons 29-30-31):

The data mule problem i.e. the TSP (1)

• (Fixed) sensor networks
• The Data Mule problem
• The TSP
  • NP-completeness
  • inapproximability
  • special cases: metric TSP and Euclidean TSP

Thursday, November 7, 2024 (Lessons 32-33):

The data mule problem i.e. the TSP (2)

• The TSP
  • generalizations

The Data Collection in ad-hoc networks i.e. the connected Dominating Set Problem

• the connected dominating set problem
• the dominating set problem
• the connected dominating set problems in unit disk graphs

Monday, November 11, 2024 (Lessons 34-35-36):

The centralized deployment of Mobile sensors i.e. the perfect matching in Bipartite graphs (1)

• (mobile) sensor networks
• The problem of centralized deployment
• The problem on graphs: min weight matching in bipartite graphs
• maximum matching in a bipartite graph (1)
  • P. Hall theorem (with proof)
  • corollary to the P. Hall theorem
  • searching for an augmenting path
  • Berge theorem on the augmenting paths
  • algorithm based on Berge theorem

Thursday, November 14, 2024 (Lessons 37-38):

The centralized deployment of Mobile sensors i.e. the perfect matching in Bipartite graphs (2)

• maximum matching in a bipartite graph (2)
  • Hopcroft & Karp algorithm
  • augmenting paths
  • an algorithm based on searching augmenting paths
  • ILP formulation
• Maximum matching in general graphs
  • blossoms
  • lemma on the cycle contraction
  • Edmonds algorithm (idea)
• Another application

Monday, November 18, 2024 (Lessons 39-40-41):

The Distributed Deployment of Sensors i.e. the Construction of a Voronoi Diagram (1)

• The problem
• A Possible Approach: Virtual Forces
• A Protocol Based on Voronoi Diagrams
• Voronoi Diagrams
  • hypothesis of general position
  • properties
  • complexity
  • the dual problem: Delaunay triangulation
• Algorithms to compute the Voronoi diagram
  • half-plane intersection (divide et impera)
  • Fortune algorithm

Thursday, November 21, 2024 (Lessons 42-43):

The Distributed Deployment of Sensors i.e. the Construction of a Voronoi Diagram (2)

• Heterogeneous sensors
  • A new notion of distance: Laguerre distance
  • Voronoi-Laguerre diagrams
  • A protocol based on Voronoi-Laguerre distance

OPIS Questionnaire. Code: KA869B9G

• guided_path_to_access_student_s_opinions_questionnaire_2024_2025_0.pdf

Monday, November 25, 2024 (Lessons 44-45-46):

Monitoring by UAVs i.e. what? (+some open problems)

• A monitoring problem
• Similar graph problems from the literature
• A novel graph problem

Other kinds of networks: the phylogeny and medicine cases (+some open problems) (1)

• Networks from biology (1)
  • Co-evolution
  • Definition of Reconciliation

Alexandra Silva's seminar. All further details can be found at https://www.di.uniroma1.it/it/notizie/seminari/distinguished-lectures

Thursday, November 28, 2024 (Lessons 47-48):

Other kinds of networks: the phylogeny and medicine cases (+some open problems) (2)

• Networks from biology (1)
  • Enumerating optimal Reconciliations
  • Visualizing reconciliations
  • Exploiting reconciliations for phylogenetic tree rooting
• Networks from medicine

Monday, December 2, 2024:

No lesson: Free time to finalize students' lessons

STUDENTS' LESSON SCHEDULE - CONFIRMED

Thursday, December 5, 2024 (Lessons 49-50):

Students' lessons on Sections 1.1 and 1.2: Federici - Coppola - Barbalata - Peral Catala

Monday, December 9, 2024 (Lessons 51-52-53):

Students' lessons on Sections 1.3, 2.1 and 2.2: Stiewe - Kuhn - Bianco - Donato - Leonardi

Thursday, December 12, 2024:

IT meeting - No lesson

Monday, December 16, 2024 (Lessons 54-55-56):

Students' lessons on Sections 3 and 4: Bandiera - Carnicella - Fuentes - Giovagnoni - Ronchetti - Bousquet

Thursday, December 19, 2024 (Lessons 62-63):

SECOND MID-TERM EXAM

Monday, December 23, 2024: NO LESSON

Lesson Diary of the Previous Years