DiarioDelleLezioni < Algoreti

---++ <b><font color="blue" size="+2">Lesson Diary A.y. 2025-2026</font></b>


%GREEN% *Monday, September 22, 2025 (Lessons 1-2-3):* %ENDCOLOR%

*FIRST DAY: WELCOME!!*

*Introduction*

*The Routing Problem, i.e., the Least Cost Path Problem (1/3)*
   * 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/2)
      * the negative cycle issue and its applications
      * least cost paths: introduction
      * Bellman-Ford algorithm
      * Dijkstra algorithm

%GREEN% *Wednesday, September 24, 2025 (Lessons 4-5):* %ENDCOLOR%

*The Routing Problem, i.e., the Least Cost Path  Problem (2/3)*

   * The least cost path Problem (2/2)
      * 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

%RED% *Monday, September 29 and Wednesday, October 1, 2025: NO Lessons* %ENDCOLOR%

%GREEN% *Monday, October 6, 2025 (Lessons 6-7-8):* %ENDCOLOR%

*The Routing Problem i.e., the Least Cost Path  Problem (3/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/2)*
   * 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
      * The Wise layout

%GREEN% *Wednesday, October 8, 2025 (Lessons 9-10):* %ENDCOLOR%

*The Problem of Laying out Interconnection Topologies, i.e., the Grid Orthogonal Drawing Problem (2/2)*
   * Layout of the Butterfly network
      * The Even & Even layout
      * comparison between the two methods
      * Optimal area layout
   * Layout of the Hypercube network
      * Collinear layout
      * general layout
   * The 3D layout problem

%GREEN% *Monday, October 13, 2025 (Lessons 11-12-13):* %ENDCOLOR%

*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
      * Model of the problem on graphs: minimum vertex cover
      * Konig-Egevary theorem (without proof)
   * A related problem: eternal vertex problem


%GREEN% *Wednesday, October 15, 2025 (Lessons 14-15):* %ENDCOLOR%

*A Frequency assignment problem i.e. the L(h,k)-Labeling Problem (1/2)*
   * 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)
      * Properties of the L(h,k)-labeling and their proofs

%GREEN% *Monday, October 20, 2025 (Lessons 16-17-18):* %ENDCOLOR%

*A Frequency assignment problem i.e. the L(h,k)-Labeling Problem (2/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
   * 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

%GREEN% *Wednesday, October 22, 2025 (Lessons 19-20):* %ENDCOLOR%


*The minimum energy broadcast, i.e., the minimum spanning tree (1/2)*
   * The Min Broadcast problem
   * NP-completeness and inapproximability results (reduction from Min Set Cover)
   * Relation between Min Broadcast and Min Spanning Tree (MST)
   * The MST problem
      * Kruskal algorithm

%GREEN% *Monday, October 27, 2025 (Lessons 21-22-23):* %ENDCOLOR%

*The minimum energy broadcast, i.e., the minimum spanning tree (2/2)*
   * The MST problem
      * Prim algorithm
      * Boruvka algorithm
   * The Min Broadcast problem
      * MST heuristics
      * SPT heuristics
      * BAIP heuristics
      * approximation ratio for MST

*The data mule problem, i.e., the TSP (1/2)*
   * (Fixed) sensor networks
   * The Data Mule problem
   * The TSP
      * NP-completeness

%GREEN% *Wednesday, October 29, 2025 (Lessons 24-25-26-27-28):* %ENDCOLOR%

*The data mule problem, i.e., the TSP (2/2)*
   * The TSP
      * 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

%RED% *Monday, November 3, 2025:* %ENDCOLOR%
NO CLASS



%RED% *Wednesday, November 5, 2025 (Lessons 29-30-31):* %ENDCOLOR%
First Mid-term exam

%GREEN% *Monday, November 10, 2026 (Lessons 32-33-34):* %ENDCOLOR%

*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's theorem (with proof)
      * searching for an augmenting path
      * Berge's theorem on the augmenting paths (with proof)

%GREEN% *Wednesday, November 12, 2026 (Lessons 35-36):* %ENDCOLOR%

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

   * maximum matching in a bipartite graph (2)
      * algorithm based on Berge's theorem
      * Hopcroft & Karp algorithm
      * augmenting paths
      * an algorithm based on searching for augmenting paths
      * ILP formulation

<!--
DIARIO GIA' COPIATO NELLA PAGINA DEGLI ANNI PRECEDENTI: SI PUO' ELIMINARE


%GREEN% *Monday, November 17, 2024 (Lessons 37-38-39):* %ENDCOLOR%

*The centralized deployment of Mobile sensors, i.e,. the perfect matching in Bipartite graphs (2)*
   * Maximum matching in general graphs
      * blossoms
      * lemma on the cycle contraction
      * Edmonds algorithm (idea)
   * Another application


%GREEN% *Wednesday, November 19, 2025 (Lessons 40-41):* %ENDCOLOR%

*The Distributed Deployment of Sensors, i.e,. the construction of a Voronoi Diagram (1/2)*

   * 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


%GREEN% *Monday, November 24, 2025 (Lessons 42-43-44):* %ENDCOLOR%

*The Distributed Deployment of Sensors, i.e,. the Construction of a Voronoi Diagram (2/2)*
   * Heterogeneous sensors
      * A new notion of distance: Laguerre distance
      * Voronoi-Laguerre diagrams
      * A protocol based on Voronoi-Laguerre distance

*OPIS Questionnaire.* Code: KA869B9G
   * [[%ATTACHURL%/guided_path_to_access_student_s_opinions_questionnaire_2024_2025_0.pdf][guided_path_to_access_student_s_opinions_questionnaire_2024_2025_0.pdf]]


%GREEN% *Wednesday, November 26, 2025 (Lessons 45-46):* %ENDCOLOR%

*Monitoring by UAVs i.e. what? (+some open problems)*
   * A monitoring problem
   * Similar graph problems from the literature
   * A novel graph problem


%GREEN% *Monday, December 1, 2025 (Lessons 47-48-49):* %ENDCOLOR%

*Other kinds of networks: the phylogeny and medicine cases (+some open problems)*
   * Networks from biology
      * Co-evolution
      * Definition of Reconciliation
      * Enumerating optimal Reconciliations
      * Visualizing reconciliations
      * Exploiting reconciliations for phylogenetic tree rooting
   * Networks from medicine


%GREEN% *Wednesday, December 3, 2025 (Lessons 50-51-52):* %ENDCOLOR%
Students' lessons on Sections 1.1 and 1.2

%RED% *Monday, December 8, 2025:* %ENDCOLOR%
Holiday


%GREEN% *Wednesday, December 10, 2025 (Lessons 53-54):* %ENDCOLOR%
Students' lessons on Sections 1.3, 2.1 and 2.2


%RED% *Monday, December 15, 2025 (Lessons 55-56-57):* %ENDCOLOR%
Students' lessons on Sections 3 and 4



%RED% *Wednesday, December 17, 2025 (Lessons 58-59-60):* %ENDCOLOR%
*SECOND MID-TERM EXAM*

-->

[[PreviousYears][Lesson Diary of the Previous Years]]

<!--

Commento
-->
This topic: Algoreti > WebHome1011 > DiarioDelleLezioni
Topic revision: r204 - 2025-11-10 - TizianaCalamoneri