Lesson Diary A.y. 2023-2024
Monday, September 25, 2023 (Lessons 1-2-3):
Introduction
The Routing Problem i.e. the Least Cost Path Problem (1)
- The routing Problem
- The shortest path Problem
- The least cost path Problem (1)
- the negative cycle issue
- least cost paths: introduction
- Bellman-Ford algorithm
- Dijkstra algorithm (part)
Thursday, September 28, 2023 (Lessons 4-5):
The Routing Problem i.e. the Least Cost Path Problem (2)
- The least cost path Problem (2)
- Dijkstra algorithm (part)
- 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, October 2, 2023 (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
- Relation between bisection width and layout area
- Layout of the Butterfly network
Thursday, October 5, 2023 (Lessons 9-10):
The Problem of Laying out Interconnection Topologies i.e. the Grid Orthogonal Drawing Problem (2)
- Layout of the Butterfly network
- The Even & Even layout
- comparison between the two methods
- Optimal area layout
Monday, October 9, 2023 (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 12, 2023 (Lessons 14-15):
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
Monday October 16, 2023 (Lessons 16-17-18):
A Frequency assignment problem i.e. the L(h,k)-Labeling Problem (2)
- 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
- 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
Thursday, October 19, 2023 (Lessons 22-23):
Special guest:
Jan Arne Telle - University of Bergen -
https://www.uib.no/en/persons/Jan.Arne.Telle
Seminar entitled:
Recognition of Linear and Star Variants of Leaf Powers is in P
Monday, October 23, 2023 (Lessons 24-25-26):
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 26, 2023 (Lessons 27-28):
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
Mid-term exam: first part
Monday, October 30, 2023 (Lessons 29-30-31):
The data mule problem i.e. the TSP
- (Fixed) sensor networks
- The Data Mule problem
- The TSP
- NP-completeness
- inapproximability
- special cases: metric TSP and Euclidean 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
Thursday, November 2, 2023 (Lessons 32-33):
The centralized deployment of Mobile sensors i.e. the perfect matching in Bipartite graphs (1)
Mid-term exam: second part
Monday November 6, 2023 (Lessons 34-35-36):
The centralized deployment of Mobile sensors i.e. the perfect matching in Bipartite graphs(2)
- The problem of centralized deployment
- The problem on graphs: min weight matching in bipartite graphs
- maximum matching in a bipartite graph
- 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
- Hopcroft & Karp algorithm
- augmenting paths
- an algorithm based on searching augmenting paths
- ILP formulation
Thursday, November 9, 2023 (Lessons 37-38):
Mid-term exam: third part
Monday November 13, 2023 (Lessons 39-40-41):
The centralized deployment of Mobile sensors i.e. the perfect matching in Bipartite graphs (3)
- Maximum matching in general graphs
- blossoms
- lemma on the cycle contraction
- Edmonds algorithm (idea)
- Another application
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
- half-plane intersection (divide et impera)
Thursday November 16, 2023 (Lessons 42-43):
The Distributed Deployment of Sensors i.e. the Construction of a Voronoi Diagram (2)
- Algorithms to compute the Voronoi diagram
students'opinions questionnaire - OPIS code: 73X3JB6A (1st year students) and SIJ1BMJY (2nd year students)
HERE: instructions for student's opinions questionnaire 2022/2023
Monday, November 20, 2023 (Lessons 44-45-46):
The Distributed Deployment of Sensors i.e. the Construction of a Voronoi Diagram (3)
- Heterogeneous sensors
- A new notion of distance: Laguerre distance
- Voronoi-Laguerre diagrams
- A protocol based on Voronoi-Laguerre distance
Monitoring by UAVs i.e. what? (+some open problems)
Thursday, November 23, 2023
Canceled
Monday, November 27, 2023 (Lessons 47-48-49):
Other kinds of networks: the phylogeny and medicine cases (+some open problems)
Thursday, November 30, 2023
Canceled
Monday, December 4, 2023 (Lessons 50-51-52):
Student lessons: Cukaj, Factor, Fiusco, Korpal, Pinna, Pro
Thursday, December 7, 2023 (Lessons 53-54):
Student lessons: Lundholm, Moldovan, Zhou
Monday, December 11, 2023 (Lessons 55-56-57):
Student lessons: Bertagnoli, D'Ambrosio, Finelli, Florescu, Gaetani, Guarini, Loffredi
Thursday, December 14, 2023
Canceled
Monday, December 18, 2023 (Lessons 58-59-60):
Mid-term exam
Lesson Diary of the Previous Years