PreviousYears < Algoreti

---++ <b><font color="blue" size="+3">Lesson Diary of the Previous Years</font></b>

---+++ <font color="red" size="+1">Lesson Diary A.y. 2023-2024</font>
---+++ *Introduction*

*The Routing Problem i.e. the Least Cost Path Problem (1)*
   * The routing Problem
   * The shortest path Problem
      * shortest paths: BFS
   * The least cost path Problem (1)
      * the negative cycle issue
      * least cost paths: introduction
      * Bellman-Ford algorithm
      * Dijkstra algorithm (part)

%GREEN% *Thursday, September 28, 2023 (Lessons 4-5):* %ENDCOLOR%

*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

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

*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
      * The Wise layout

%GREEN% *Thursday, October 5, 2023 (Lessons 9-10):* %ENDCOLOR%

*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

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

*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

%GREEN% *Thursday October 12, 2023 (Lessons 14-15):* %ENDCOLOR%

*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

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

*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

%GREEN% *Thursday, October 19, 2023 (Lessons 22-23):* %ENDCOLOR%

*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

%GREEN% *Monday, October 23, 2023 (Lessons 24-25-26):* %ENDCOLOR%
*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)

%GREEN% *Thursday, October 26, 2023 (Lessons 27-28):* %ENDCOLOR%

*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

%RED% *Mid-term exam: first part* %ENDCOLOR%

%GREEN% *Monday, October 30, 2023 (Lessons 29-30-31):* %ENDCOLOR%

*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

%GREEN% *Thursday, November 2, 2023 (Lessons 32-33):* %ENDCOLOR%

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

%RED% *Mid-term exam: second part* %ENDCOLOR%

%GREEN% *Monday November 6, 2023 (Lessons 34-35-36):* %ENDCOLOR%

*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

%GREEN% *Thursday, November 9, 2023 (Lessons 37-38):* %ENDCOLOR%

%RED% *Mid-term exam: third part* %ENDCOLOR%

%GREEN% *Monday November 13, 2023 (Lessons 39-40-41):* %ENDCOLOR%

*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)

%GREEN% *Thursday November 16, 2023 (Lessons 42-43):* %ENDCOLOR%

*The Distributed Deployment of Sensors i.e. the Construction of a Voronoi Diagram (2)*
   * Algorithms to compute the Voronoi diagram
      * Fortune algorithm

%RED%students'opinions questionnaire - OPIS code: 73X3JB6A (1st year students) and SIJ1BMJY (2nd year students) %ENDCOLOR%

[[%ATTACHURL%/guided_path_to_access_student_s_opinions_questionnaire_2022_2023.pdf][HERE]]: instructions for student's opinions questionnaire 2022/2023

%GREEN% *Monday, November 20, 2023 (Lessons 44-45-46):* %ENDCOLOR%
*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)*

%RED% *Thursday, November 23, 2023* %ENDCOLOR%
*Canceled*

%GREEN% *Monday, November 27, 2023 (Lessons 47-48-49):* %ENDCOLOR%
*Other kinds of networks: the phylogeny and medicine cases (+some open problems)*

%RED% *Thursday, November 30, 2023* %ENDCOLOR%
*Canceled*

%GREEN% *Monday, December 4, 2023 (Lessons 50-51-52):* %ENDCOLOR%
*Student lessons*: Cukaj, Factor, Fiusco, Korpal, Pinna, Pro

%GREEN% *Thursday, December 7, 2023 (Lessons 53-54):* %ENDCOLOR%
*Student lessons*: Lundholm, Moldovan, Zhou

%GREEN% *Monday, December 11, 2023 (Lessons 55-56-57):* %ENDCOLOR%
*Student lessons*: Bertagnoli, D'Ambrosio, Finelli, Florescu, Gaetani, Guarini, Loffredi

%RED% *Thursday, December 14, 2023* %ENDCOLOR%
*Canceled*

%GREEN% *Monday, December 18, 2023 (Lessons 58-59-60):* %ENDCOLOR%

%RED% *Mid-term exam* %ENDCOLOR%

---+++ <font color="red" size="+1">Lesson Diary A.y. 2022-2023</font>
---+++ %GREEN% *Tuesday September 27, 2022 (Lessons 1-2-3):* %ENDCOLOR%

*Introduction*

*The Routing Problem i.e. the Least Cost Path Problem (1)*
   * The routing Problem
   * The shortest path Problem
      * shortest paths: BFS
   * The least cost path Problem (1)
      * the negative cycle issue
      * least cost paths: introduction
      * Bellman-Ford algorithm
      * Dijkstra algorithm

%GREEN% *Friday September 30, 2022 (Lessons 4-5):* %ENDCOLOR%

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

   * The least cost path Problem (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
      * the Benes network
      * routing on the Benes network: the looping algorithm

%GREEN% *Tuesday October 4, 2022 (Lessons 6-7-8):* %ENDCOLOR%

*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
      * the Wise layout
      * the Even & Even layout
      * comparison between the two methods

%GREEN% *Friday October 7, 2022 (Lessons 9-10):* %ENDCOLOR%

*The Problem of Laying out Interconnection Topologies i.e. the Grid Orthogonal Drawing Problem (3)*
   * Layout of the Butterfly network
      * Optimal area layout
   * Layout of the Hypercube network
      * Collinear layout
      * general layout
   * The 3D layout problem

%GREEN% *Tuesday October 11, 2022 (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 with vertex cover
      * another approximation algorithm
      * Konig-Egevary theorem (without proof)
   * A related problem: eternal vertex problem

%GREEN% *Friday October 14, 2022 (Lessons 14-15):* %ENDCOLOR%

*The Problem of Minimizing Boolean Circuits i.e. the Minimum Set Covering Problem*
   * The problem of minimizing boolean functions
   * Model of the problem on graphs: the Minimum Set Cover Problem
      * definition
      * ILP formulation
      * relation with the Minimum Vertex Covering Problem
      * an O(log n)-approximation algorithm
      * another approximation algorithm
      * some related problems:
         * Hitting set problem
         * Edge Cover problem
         * Set Packing problem
         * Exact Cover problem

*A Frequency assignment problem i.e. the L(h,k)-Labeling Problem (1)*
   * Introduction to the frequency assignment problems

%GREEN% *Tuesday October 18, 2022 (Lessons 16-17-18):* %ENDCOLOR%

*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 suqre of a graph
      * Properties of the L(h,k)-labeling and their proofs
      * Proof of NP-completeness for diameter 2 graphs

%GREEN% *Friday October 21, 2022 (Lessons 19-20):* %ENDCOLOR%

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

%GREEN% *Tuesday October 25, 2022 (Lessons 21-22-23):* %ENDCOLOR%

%BLUE% students' lesson 1: The Routing problem i.e. the minimum cost shortest path %ENDCOLOR%

%BLUE% students' lesson 2: The layout of interconnection networks i.e. the orthogonal grid graph drawing %ENDCOLOR%

*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
      * frequency assignment in GSM networks
   * a parenthesis on the 4 color theorem

%GREEN% *Friday October 28, 2022 (Lessons 24-25):* %ENDCOLOR%

*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)
   * The MST problem
      * Kruskal algorithm
      * Prim algorithm
      * Boruvka algorithm

%RED% *Tuesday November 1, 2022: HOLIDAY* %ENDCOLOR%

%GREEN% *Friday November 4, 2022 (Lessons 26-27):* %ENDCOLOR%

%BLUE% students' lesson 3: The problem of infecting a network with a worm i.e. the minimum vertex cover problem %ENDCOLOR%

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

*The data mule problem i.e. the TSP (1)*
   * (Fixed) sensor networks
   * The Data Mule problem

%GREEN% *Tuesday November 8, 2022 (Lessons 28-29-30):* %ENDCOLOR%

%BLUE% students' lesson 4: The problem of minimizing a boolean circuit i.e. the minimum set covering problem %ENDCOLOR%

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

%RED% *Friday November 11, 2022 (Lessons 31-32-33): FIRS MID-TERM EXAM* %ENDCOLOR%

%GREEN% *Tuesday November 15, 2022 (Lessons 34-35-36):* %ENDCOLOR%

%BLUE% students' lesson 5: The frequency assignment problem i.e. a graph coloring problem %ENDCOLOR%

%BLUE% students' lesson 6: The minimum energy broadcast problem i.e. the minimum spanning tree problem %ENDCOLOR%

*the Data Collection in ad-hoc networks i.e. the connected Dominating Set Problem (2)*
   * the connected dominating set problem
   * the dominating set problem
   * the connected dominating set problems in unit disk graphs

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

%GREEN% *Friday November 18, 2022 (Lessons 37-38):* %ENDCOLOR%

*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 a bipartite graphs
   * maximum matching in a bipartite graph
      * P. Hall theorem (with proof)
      * corollary to the P. Hall theorem
      * searching an augmenting path
      * Berge theorem on the augmenting paths
      * algorithm based on Berge theorem
      * Hopcroft & Karp algorithm

%GREEN% *Tuesday November 22, 2022 (Lessons 39-40-41):* %ENDCOLOR%

%BLUE% students' lesson 7: The data mule scheduling problem i.e. the travelling salesman problem %ENDCOLOR%

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

   * Minimum weight perfect matching in bipartite graphs (cntd)
      * 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

%GREEN% *Friday November 25, 2022 (Lessons 42-43):* %ENDCOLOR%

*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
      * hypthesis of general position
      * properties
      * complexity
      * the dual problem: Delaunay triangulation

%GREEN% *Tuesday November 29, 2022 (Lessons 44-45-46):* %ENDCOLOR%

%BLUE% students' lesson 8: The centralized deployment of a mobile sensor network i.e. the minimum cost perfect matching in bipartite graphs %ENDCOLOR%

%RED%students'opinions questionnaire - OPIS code: R053WYBC %ENDCOLOR%

*The Distributed Deployment of Sensors i.e. the Construction of a Voronoi Diagram (2)*
   * Algorithms to compute the Voronoi diagram
      * half-plane intersection (divide et impera)
      * Fortune algorithm

%GREEN% *Friday December 2, 2022 (Lessons 47-48):* %ENDCOLOR%

*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

%GREEN% *Tuesday December 6, 2022 (Lessons 49-50-51):* %ENDCOLOR%

%BLUE% students' lesson 9: Self-deployment of a mobile sensor network i.e. the Voronoi Diagram %ENDCOLOR%

*Monitoring by UAVs i.e. the multiple TSP with constraints*

%RED% *Friday December 9, 2022: LONG WEEKEND: the University is closed* %ENDCOLOR%

%GREEN% *Tuesday December 13, 2022 (Lessons 52-53-54)* %ENDCOLOR%

%BLUE% students' lesson 10: Monitoring by UAVs i.e. the multiple TSP with constraints %ENDCOLOR%

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

%RED% *Friday December 16, 2022 (Lessons 55-56): no lesson* %ENDCOLOR%

%RED% *Tuesday December 20, 2022 (Lessons 57-58-59): SECOND
 MID-TERM EXAM* %ENDCOLOR%

---++ <font color="red" size="+3">Lesson Diary A.y. 2021-2022</font>

%GREEN% *Wednesday September 22, 2021 (Lessons 1-2-3):* %ENDCOLOR%

*Introduction*

*The Routing Problem i.e. the Least Cost Path Problem (1)*
   * The routing Problem
   * The shortest path Problem
      * shortest paths: BFS
   * The least cost path Problem
      * the negative cycle issue
      * least cost paths: introduction

%GREEN% *Friday September 24, 2021:* %ENDCOLOR%

*No lesson*

%GREEN% *Wednesday September 29, 2021 (Lessons 4-5-6):* %ENDCOLOR%

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

   * The least cost path Problem
      * Bellman-Ford algorithm
      * 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

%GREEN% *Friday October 1, 2021 (Lessons 7-8):* %ENDCOLOR%

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

   * The Routing Problem on Interconnection Topologies
      * the concept of blocking network, non-blocking network and rearrangeable network
      * 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

%GREEN% *Wednesday October 6, 2021 (Lessons 9-10-11):* %ENDCOLOR%

*The Problem of Laying out Interconnection Topologies i.e. the Grid Orthogonal Drawing Problem (2)*
   * 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
      * the Even & Even layout

%GREEN% *Friday October 8, 2021 (Lessons 12-13):* %ENDCOLOR%

*The Problem of Laying out Interconnection Topologies i.e. the Grid Orthogonal Drawing Problem (3)*
   * Layout of the Butterfly network
      * summary of the last lesson hour (the video went lost)
      * comparison between the two methods
   * Layout of the Hypercube network
      * Collinear layout
      * general layout
   * The 3D layout problem

%GREEN% *Wednesday October 13, 2021 (Lessons 14-15-16):* %ENDCOLOR%

*A parenthesis: Some problems in (co-)phylogeny (some theses' proposals)*

*The problem of worm propagation/prevention i.e. the Minimum Vertex Covering Problem (2)*
   * The problem
      * worms
      * damages caused by worms

%GREEN% *Friday October 15, 2021 (Lessons 17-18):* %ENDCOLOR%

*The problem of worm propagation/prevention i.e. the Minimum Vertex Covering Problem (2)*
   * Model of the problem on graphs: minimum vertex cover
      * definition
      * ILP model
      * a 2-approximation algorithm
      * independent set and maximum matching in relation with vertex cover
      * another approximation algorithm
      * Konig-Egevary theorem (without proof)
   * A related problem: eternal vertex problem

%GREEN% *Wednesday October 20, 2021 (Lessons 19-20-21):* %ENDCOLOR%

*The Problem of Minimizing Boolean Circuits i.e. the Minimum Set Covering Problem*
   * The problem of minimizing boolean functions
   * Model of the problem on graphs: the Minimum Set Cover Problem
      * definition
      * ILP formulation
      * relation with the Minimum Vertex Covering Problem
      * an O(log n)-approximation algorithm
      * another approximation algorithm
      * some related problems:
         * Hitting set problem
         * Edge Cover problem
         * Set Packing problem
         * Exact Cover 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

%GREEN% *Friday October 22, 2021 (Lessons 22-23):* %ENDCOLOR%

*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
   * L(h,k)-labeling and minimum span (1)
      * The special case h=k in relation to the suqre of a graph
      * Properties of the L(h,k)-labeling and their proofs
      * Proof of NP-completeness for diameter 2 graphs (first part)

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

*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 lambbda
      * 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

%GREEN% *Friday October 29, 2021 (Lessons 27-28-29):* %ENDCOLOR%

*A Frequency assignment problem i.e. the L(h,k)-Labeling Problem (3)*
   * L(h,k)-labeling and minimum span (3)
      * Approximate results: outerplanar graphs
   * Variations of the problem (1)
      * oriented L(2,1)-labeling
      * L(h1, ..., hk)-labeling
      * backbone coloring
      * multiple L(h,k)-labeling
      * frequency assignment in GSM networks

%GREEN% *Week November 2-5, 2021: Mid-term exams* %ENDCOLOR%

%GREEN% *Wednesday November 10, 2021 (Lessons 30-31-32):* %ENDCOLOR%
*A Frequency assignment problem i.e. the L(h,k)-Labeling Problem (4)*
   * L(h,k)-labeling and minimum span (4)
   * Variations of the problem (2)
   * 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)

%GREEN% *Friday November 12, 2021 (Lessons 33-34):* %ENDCOLOR%
*The minimum energy broadcast i.e. the minimum spanning tree (2)*

   * The MST problem
      * Kruskal algorithm
      * Prim algorithm
      * Boruvka algorithm

%GREEN% *Wednesday November 17, 2021 (Lessons 35-36-37):* %ENDCOLOR%

*The minimum energy broadcast i.e. the minimum spanning tree (3)*
   * the Min Broadcast problem
      * MST heuristics
      * SPT heuristics
      * BAIP heuristics
      * approximation ratio for MST

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

   * (Fixed) sensor networks
   * The Data Mule problem
   * The TSP
      * NP-completeness
      * inapproximability

%GREEN% *Friday November 19, 2021 (Lessons 38-39):* %ENDCOLOR%

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

   * 
      * special cases: metric TSP and Euclidean TSP
      * generalizations

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

   * (mobile) sensor networks

%GREEN% *Wednesday November 24, 2021 (Lessons 40-41-42):* %ENDCOLOR%

*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 a bipartite graphs
   * maximum matching in a bipartite graph
      * P. Hall theorem (with proof)
      * corollary to the P. Hall theorem
      * searching an augmenting path
      * Berge theorem on the augmenting paths
      * algorithm based on Berge theorem
      * Hopcroft & Karp algorithm

%GREEN% *Friday November 26, 2021 (Lessons 43-44):* %ENDCOLOR%

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

   * Minimum weight perfect matching in bipartite graphs (cntd)
      * 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

%GREEN% *Wednesday December 1, 2021 (Lessons 45-46-47):* %ENDCOLOR%

%RED% *Students' lessons* %ENDCOLOR%

*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
      * hypthesis of general position
      * properties
      * complexity
      * the dual problem: Delaunay triangulation

%GREEN% *Friday December 3, 2021 (Lessons 48-49):* %ENDCOLOR%

%RED% *Students' lessons* [BKTL04], [BPT00], [Bal07], [AGK08], [Xal14] %ENDCOLOR%

%RED% *Wednesday December 8, 2021: HOLIDAY* %ENDCOLOR%

%GREEN% *Friday December 10, 2021 (Lessons 50-51):* %ENDCOLOR%

%RED% *Students' lessons* [M95], [Cal15]  %ENDCOLOR%

*The Distributed Deployment of Sensors i.e. the Construction of a Voronoi Diagram (2)*
   * Algorithms to compute the Voronoi diagram
      * half-plane intersection (divide et impera)
      * Fortune algorithm

%GREEN% *Wednesday December 15, 2021 (Lessons 52-53-54):* %ENDCOLOR%

%RED% *Students' lessons* [HZ14], [YWD06], [NSM16], [ML18]  %ENDCOLOR%

*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 theses' proposals)*

%GREEN% *Friday December 17, 2021 (Lessons 55-56): mid-term exam* %ENDCOLOR%

%GREEN% *Wednesday December 22, 2021: no lesson* %ENDCOLOR%

--
---+ %RED%Lesson Diary A.y. 2020-2021%ENDCOLOR%

%GREEN% *Wednesday October 7, 2020 (Lessons 1-2-3):* %ENDCOLOR%

*Introduction*

*The Routing Problem i.e. the Least Cost Path Problem (1)*
   * The routing Problem
   * The shortest path Problem
      * shortest paths: BFS
   * The least cost path Problem
      * the negative cycle issue
      * least cost paths: introduction

%GREEN% *Friday October 9, 2020 (Lessons 4-5):* %ENDCOLOR%

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

   * The least cost path Problem
      * Bellman-Ford algorithm
      * 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

%GREEN% *Wednesday October 14, 2020 (Lessons 6-7-8):* %ENDCOLOR%

*The Routing Problem i.e. the Shortest Path Problem (3)*
   * The Routing Problem on Interconnection Topologies (2)
      * the concept of blocking network, non-blocking network and rearrangeable network
      * 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
   * 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% *Friday October 16, 2020 (Lessons 9-10):* %ENDCOLOR%

*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
   * Layout of the Hypercube network
      * Collinear layout
      * general layout
   * The 3D layout problem

%GREEN% *Wednesday October 21, 2020 (lessons 11-12-13):*
%ENDCOLOR%

*The problem of worm propagation/prevention i.e. the Minimum Vertex Covering Problem*
   * 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 with vertex cover
      * another approximation algorithm
      * Konig-Egevary theorem (without proof)
   * A related problem: eternal vertex problem

%GREEN% *Friday October 23, 2020 (lessons 14-15):*
%ENDCOLOR%

*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
   * L(h,k)-labeling and minimum span (1)
      * The special case h=k in relation to the suqre of a graph
      * Properties of the L(h,k)-labeling and their proofs

%GREEN% <b>Wednesday October 28, 2020 (lessons 16-17-18):*
</b>%ENDCOLOR%
*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 lambbda
      * 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
      * Approximate results: outerplanar graphs
   * Variations of the problem
      * oriented L(2,1)-labeling
      * L(h1, ..., hk)-labeling
      * backbone coloring
      * multiple L(h,k)-labeling
      * frequency assignment in GSM networks
   * a parenthesis on the 4 color theorem

%GREEN% *Friday October 30, 2020 (lessons 19-20):*
%ENDCOLOR%

*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)

%GREEN% *Wednesday November 4, 2020 (lessons 21-22-23):*
%ENDCOLOR%

*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 SPT

%GREEN%
*Friday November 6, 2020  (lessons 24-25):*
%ENDCOLOR%

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

   * (Fixed) sensor networks
   * The Data Mule problem
   * The TSP
      * NP-completeness
      * inapproximability

%GREEN%
*Wednesday November 11, 2020  (lessons 26-27-28):*
%ENDCOLOR%

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

   * 
      * special cases: metric TSP and Euclidean TSP
      * generalizations

*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 a bipartite graphs
   * maximum matching in a bipartite graph
      * P. Hall theorem (with proof)
      * corollary to the P. Hall theorem
      * searching an augmenting path

%GREEN%
*Friday November 13, 2020  (lessons 29-30):*
%ENDCOLOR%

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

   * maximum matching in a bipartite graph (cntd)
      * Berge theorem on the augmenting paths
      * algorithm based on Berge theorem
      * Hopcroft & Karp algorithm
   * Minimum weight perfect matching in bipartite graphs
      * augmenting paths
      * an algorithm based on searching augmenting paths
      * ILP formulation
   * Maximum matching in general graphs
      * blossoms
      * lemma on the cycle contraction

%GREEN%
*Wednesday November 18, 2020  (lessons 31-32-33):*
%ENDCOLOR%

*Students' lessons (1)*

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

   * Maximum matching in general graphs (cntd)
      * blossoms
      * lemma on the cycle contraction
      * Edmonds algorithm (idea)

*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
      * hypthesis of general position

%GREEN%
*Friday November 20, 2020  (lessons 34-35):*
%ENDCOLOR%

*The Distributed Deployment of Sensors i.e. the Construction of a Voronoi Diagram (2)*
   * Voronoi Diagrams (cntd)
      * properties
      * complexity
      * the dual problem: Delaunay triangulation
   * Algorithms to compute the Voronoi diagram (1)
      * half-plane intersection (divide et impera)

%GREEN%
*Wednesday November 25, 2020  (lessons 36-37-38):*
%ENDCOLOR%

*Students' lessons (2)*

*The Distributed Deployment of Sensors i.e. the Construction of a Voronoi Diagram (3)*
   * Voronoi Diagrams (cntd)
      * Fortune algorithm
   * Heterogeneous sensors
      * A new notion of distance: Laguerre distance
      * Voronoi-Laguerre diagrams
      * A protocol based on Voronoi-Laguerre distance

%GREEN%
*Friday November 27, 2020  (lessons 39-40):*
%ENDCOLOR%

*Mid Term Exam 1/2*

%GREEN%
*Wednesday December 2, 2020  (lessons 41-42-43):*
%ENDCOLOR%

*Students' lessons (3)*

*The Problem of Minimizing Boolean Circuits i.e. the Minimum Set Covering Problem*
   * The problem of minimizing boolean functions
   * Model of the problem on graphs: the Minimum Set Cover Problem
      * definition
      * ILP formulation
      * relation with the Minimum Vertex Covering Problem
      * an O(log n)-approximation algorithm
      * another approximation algorithm
      * some related problems:
         * Hitting set problem
         * Edge Cover problem
         * Set Packing problem
         * Exact Cover problem

%GREEN%
*Friday December 4, 2020  (lessons 44-45):*
%ENDCOLOR%

*Monitoring by UAVs i.e. what? (some theses' proposals)*

%GREEN%
*Wednesday December 9, 2020 (lessons 46-47-48):*
%ENDCOLOR%

*Students' lessons (4)*

   * Dr. Federico Corò: "A Realistic Model to Support Rescue Operationsby UAVs after an Earthquake"

%GREEN%
*Friday December 11, 2020  (lessons 49-50):*
%ENDCOLOR%

*Some problems in (co-)phylogeny (some further theses' proposals)*

%GREEN%
*Wednesday December 16, 2020 (lessons 51-52-53):*
%ENDCOLOR%

*Students' lessons (5)*

%GREEN%
*Friday December 18, 2020  (lessons 54-55):*
%ENDCOLOR%

*Mid Term Exam 2/2*

----

---++ <font color="red" size="+3">Lesson Diary A.y. 2019-2020</font>

%GREEN% *Wednesday September 25, 2019 (Lessons 1-2-3):* %ENDCOLOR%

*Introduction*

*The Routing Problem i.e. the Least Cost Path Problem (1)*
   * The routing Problem
   * The shortest path Problem
      * shortest paths: BFS
   * The least cost path Problem
      * the negative cycle issue
      * least cost paths: introduction
      * Bellman-Ford algorithm
      * Dijkstra algorithm
      * Floyd-Warshall algorithm

%GREEN% *Friday September 27, 2019 (Lessons 4-5):* %ENDCOLOR%

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

   * 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
      * the Benes network
      * routing on the Benes network: the looping algorithm

%GREEN% *Wednesday October 2, 2019 (Lessons 6-7-8):* %ENDCOLOR%

*The Routing Problem i.e. the Shortest Path Problem (3)*
   * The Routing Problem on Interconnection Topologies (2)
      * 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
   * Collinear Layout of the Complete network
   * Layout of the Complete network
   * Relation between bisection width and layout area

%GREEN% *Friday October 4, 2019 (lessons 9-10):*
%ENDCOLOR%

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

%GREEN% *Wednesday October 9, 2019 (lessons 11-13):*
%ENDCOLOR%

*The problem of worm propagation/prevention i.e. the Minimum Vertex Covering Problem*
   * 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 with vertex cover
      * another approximation algorithm
      * Konig-Egevary theorem

%GREEN% *Friday October 11, 2019 (lessons 14-15):*
%ENDCOLOR%

*The Problem of Minimizing Boolean Circuits i.e. the Minimum Set Covering Problem*
   * The problem of minimizing boolean functions
   * Model of the problem on graphs: the Minimum Set Cover Problem
      * definition
      * ILP formulation
      * relation with the Minimum Vertex Covering Problem
      * an O(log n)-approximation algorithm
      * another approximation algorithm
      * some related problems:
         * Hitting set problem
         * Edge Cover problem
         * Set Packing problem
         * Exact Cover problem

*A Frequency assignment problem i.e. the L(h,k)-Labeling Problem (1)*
   * Introduction to the frequency assignment problems

%GREEN% *Wednesday October 16, 2019 (lessons 16-18):*
%ENDCOLOR%

*A Frequency assignment problem i.e. the L(h,k)-Labeling Problem (2)*
   * Direct and hidden collisions, interference graph
   * L(h,k)-labeling and minimum span (1)
      * The special case h=k in relation to the suqre of a graph
      * Properties of the L(h,k)-labeling and their proofs
      * Proof of NP-completeness for diameter 2 graphs

%GREEN% *Friday October 18, 2019 (lessons 19-20):*
%ENDCOLOR%

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

   * L(h,k)-labeling and minimum span (2)
      * Lower bound of Delta+1 on lambbda
      * 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
      * Approximate results: outerplanar graphs

%GREEN% *Wednesday October 23, 2019 (lessons 21-23):*
%ENDCOLOR%

Lesson cancelled (due to illness of the teacher)

%GREEN% *Friday October 25, 2019 (lessons 24-25):*
%ENDCOLOR%

*A Frequency assignment problem i.e. the L(h,k)-Labeling Problem (4)*
   * Variations of the problem
      * oriented L(2,1)-labeling
      * L(h1, ..., hk)-labeling
      * backbone coloring
      * multiple L(h,k)-labeling
      * frequency assignment in GSM networks
   * 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)

%GREEN% *Wednesday October 29, 2019 (lessons 26-28):*
%ENDCOLOR%

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

   * The MST problem
      * Kruskal algorithm
      * Prim algorithm
      * Boruvka algorithm
   * the Min Broadcast broblem
      * MST euristic
      * SPT euristic
      * BAIP euristic
      * approximation ratio for SPT

%GREEN% *Friday November 1, 2019 (lessons 26-27):*
%ENDCOLOR%

Holiday

%GREEN% *Wednesday November 6, 2019 (lessons 28-30):*
%ENDCOLOR%

Midterm Exam

%GREEN%
*Friday November 8, 2019  (lessons 31-32):*
%ENDCOLOR%

*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

%GREEN% *Wednesday November 13, 2019 (lessons 33-35):*
%ENDCOLOR%

*Student Lessons with the presence of the teacher (1)*

see http://twiki.di.uniroma1.it/twiki/view/Algoreti/ProgrammaLezioniDegliStudenti

*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 a bipartite graphs

%GREEN% *Friday November 15, 2019 (lessons 36-37):*
%ENDCOLOR%

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

   * maximum matching in a bipartite graph
      * P. Hall theorem (with proof)
      * corollary to the P. Hall theorem
      * searching an augmenting path
      * Berge theorem on the augmenting paths
      * algorithm based on Berge theorem
      * Hopcroft & Karp algorithm
   * Minimum weight perfect matching in bipartite graphs
      * augmenting paths
      * an algorithm based on searching augmenting paths
      * ILP formulation

%GREEN% *Wednesday November 20, 2019 (lessons 38-40):*
%ENDCOLOR%

*Student Lessons with the presence of the teacher (2)*

see http://twiki.di.uniroma1.it/twiki/view/Algoreti/ProgrammaLezioniDegliStudenti

*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)

*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

%GREEN% <b>Friday November 22, 2019 (lessons 41-42):*
</b>%ENDCOLOR%
*The Distributed Deployment of Sensors i.e. the Construction of a Voronoi Diagram (2)

   * Voronoi Diagrams
      * hypthesis of general position
      * properties
      * complexity
      * the dual problem: Delaunay triangulation
   * Algorithms to compute the Voronoi diagram (1)
      * half-plane intersection (divide et impera)

%GREEN% *Wednesday November 27, 2019 (lessons 43-45):*
%ENDCOLOR%

*Student Lessons with the presence of the teacher (3)*

see http://twiki.di.uniroma1.it/twiki/view/Algoreti/ProgrammaLezioniDegliStudenti

*EVALUATION OF THE COURSE*

%GREEN% *Friday November 29, 2019 (lessons 46-47):*
%ENDCOLOR%

*The Distributed Deployment of Sensors i.e. the Construction of a Voronoi Diagram (3)*
   * Algorithms to compute the Voronoi diagram (2)
      * Fortune algorithm

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

%GREEN% *Wednesday December 4, 2019 (lessons 48-50):*
%ENDCOLOR%

*Student Lessons with the presence of the teacher (4)*

see http://twiki.di.uniroma1.it/twiki/view/Algoreti/ProgrammaLezioniDegliStudenti

*Monitoring by UAVs i.e. what? (some theses' proposals)*

%GREEN% *Friday December 6, 2019 (lessons 51-52):*
%ENDCOLOR%

*Some problems in (co-)phylogeny (some further theses' proposals)*

%GREEN% *Wednesday December 11, 2019 (lessons 51-53):*
%ENDCOLOR%

*Student Lessons with the presence of the teacher (5)*

see http://twiki.di.uniroma1.it/twiki/view/Algoreti/ProgrammaLezioniDegliStudenti

%RED% Winner Announcement: Award for the best students' lesson%ENDCOLOR%

%GREEN% *Friday December 13, 2019 (lessons 53-54):*
%ENDCOLOR%

*Phylogenetic Networks* by Prof. B. Sinaimeri (INRIA Grenoble)

%GREEN% *Wednesday December 18, 2019 (lessons 55-57):*
%ENDCOLOR%

Midterm Exam

---++ <font color="red" size="+3">Lesson Diary A.y. 2018-2019</font>

%RED%
*Tuesday September 25, 2018 (Lessons 1-2,5):*
%ENDCOLOR%

*Introduction*

*The Routing Problem i.e. the Shortest Path Problem (1)*
   * The routing Problem
   * The shortest path Problem (1)
      * shortest paths: BFS
      * the negative cycle issue
      * least cost paths: introduction

%RED%
*Thursday September 27, 2018 (Lessons 2,5-5):*
%ENDCOLOR%

*The Routing Problem i.e. the Shortest Path Problem (2)*
   * The shortest path Problem (2)
      * least cost paths (cnt.d):
        * Bellman-Ford algorithm
         * Dijkstra algorithm
         * Floyd-Warshall algorithm
   * The Routing Problem on Interconnection Topologies (1)
      * 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%
*Tuesday October 2, 2018 (Lessons 5-7,5):*
%ENDCOLOR%

*The Routing Problem i.e. the Shortest Path Problem (3)*
   * The Routing Problem on Interconnection Topologies (2)
      * 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
   * Collinear Layout of the Complete network
   * Layout of the Complete network

%RED%
*Thursday October 4, 2018 (lessons 7,5-10):*
%ENDCOLOR%

*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 (1)
      * the Wise layout
      * the Even & Even layout
      * comparison between the two methods

%RED%
*Tuesday October 9, 2018 (lessons 10-12,5):*
%ENDCOLOR%

*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 (1)
      * definition
      * ILP model

%RED%
*Thursday October 11, 2018 (lessons 12,5-15):*
%ENDCOLOR%

*The problem of worm propagation/prevention i.e. the Minimum Vertex Covering Problem (2)*
   * Model of the problem on graphs: minimum vertex cover (2)
      * a 2-approximation algorithm
      * independent set and maximum matching in relation with vertex cover
      * another approximation algorithm
      * Konig-Egevary theorem

%RED%
*Tuesday October 16, 2018 (lessons 15-17,5):*
%ENDCOLOR%

*The Problem of Minimizing Boolean Circuits i.e. the Minimum Set Covering Problem*
   * The problem of minimizing boolean functions
   * Model of the problem on graphs: the Minimum Set Cover Problem
      * definition
      * ILP formulation
      * relation with the Minimum Vertex Covering Problem
      * an O(log n)-approximation algorithm
      * another approximation algorithm
      * some related problems:
         * Hitting set problem
         * Edge Cover problem
         * Set Packing problem
         * Exact Cover problem

*A Frequency assignment problem i.e. the L(h,k)-Labeling Problem (1)*
   * Introduction to the frequency assignment problems

%RED%
*Thursday October 18, 2018 (lessons 17,5-20):*
%ENDCOLOR%

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

%BLUE%
*Tuesday October 23, 2018  (lessons 20-22,5):*
%ENDCOLOR%

*Student Lessons with the presence of the teacher (1)*

see http://twiki.di.uniroma1.it/twiki/view/Algoreti/ProgrammaLezioniDegliStudenti

%RED%
*Thursday October 25, 2018 (lessons 22,5-25):*
%ENDCOLOR%

*A Frequency assignment problem i.e. the L(h,k)-Labeling Problem (3)*
   * L(h,k)-labeling and minimum span (2)
      * Lower bound of Delta+1 on lambbda
      * 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

%RED%
*Tuesday October 30, 2018:* %ENDCOLOR%

Lesson canceled by the Dean.

%RED%
*Thursday November 1, 2018:* %ENDCOLOR%

Holiday.

%RED%
*Tuesday November 6, 2018 (lessons 25-27,5):*
%ENDCOLOR%

*A Frequency assignment problem i.e. the L(h,k)-Labeling Problem (4)*
   * L(h,k)-labeling and minimum span (3)
      * Approximate results: outerplanar graphs
   * variations of the problem
      * oriented L(2,1)-labeling
      * L(h1, ..., hk)-labeling
      * backbone coloring
      * multiple L(h,k)-labeling
      * frequency assignment in GSM networks
   * 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)

%BLUE%
*Thursday November 8, 2018  (lessons 27,5-30):*
%ENDCOLOR%

*Mid term exam*

%BLUE%
*Tuesday November 13, 2018  (lessons 30-32,5):*
%ENDCOLOR%

*Student Lessons with the presence of the teacher (2)*

see http://twiki.di.uniroma1.it/twiki/view/Algoreti/ProgrammaLezioniDegliStudenti

%RED%
*Thursday November 15, 2018  (lessons 32,5-35):*
%ENDCOLOR%

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

   * The MST problem
      * Kruskal algorithm
      * Prim algorithm
      * Boruvka algorithm
   * the Min Broadcast broblem
      * MST euristic
      * SPT euristic
      * BAIP euristic
      * approximation ratio for SPT

%RED%
*Tuesday November 20, 2018  (lessons 35-37,5):*
%ENDCOLOR%

*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

%RED%
*Thursday November 22, 2018  (lessons 37,5-40):*
%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 a bipartite graphs
   * maximum matching in a bipartite graph
      * P. Hall theorem (with proof)
      * corollary to the P. Hall theorem
      * searching an augmenting path
      * Berge theorem on the augmenting paths
      * algorithm based on Berge theorem
      * Hopcroft & Karp algorithm

%RED%
*Tuesday November 27, 2018:*
%ENDCOLOR%

*NO LESSON*

%RED%
*Thursday November 29, 2018  (lessons 40-42,5):*
%ENDCOLOR%
*The centralized deployment of Mobile sensors i.e. the perfect matching in Bipartite graphs (2)*

   * Minimum weight perfect matching in bipartite graphs
      * 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)

*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

*EVALUATION OF THE COURSE*

%RED%
*Tuesday December 4, 2018  (lessons 42,5-45):*
%ENDCOLOR%

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

   * Voronoi Diagrams
      * hypthesis of general position
      * properties
      * complexity
      * the dual problem: Delaunay triangulation
   * Algorithms to compute the Voronoi diagram
      * half-plane intersection (divide et impera)
      * Fortune's algorithm

%GREEN%
*Thursday December 6, 2018  (lessons 45-47,5):*
%ENDCOLOR%

*Distributed Deployment 2*

%BLUE%
*Tuesday December 11, 2018  (lessons 47,5-50):*
%ENDCOLOR%

*Student Lessons with the presence of the teacher (3)*

see http://twiki.di.uniroma1.it/twiki/view/Algoreti/ProgrammaLezioniDegliStudenti

%GREEN%
*Thursday December 13, 2018  (lessons 50-52,5):*
%ENDCOLOR%

*UAVs 1*

%BLUE%
*Tuesday December 18, 2018  (lessons 52,5-55):*
%ENDCOLOR%

*UAVs 2 (Prof. S. Silvestri - University of Kentucky Computer Science)*

%BLUE%
*Tuesday December 20, 2018  (lessons 55-57,5):*
%ENDCOLOR%

*Student Lessons with the presence of the teacher (4)*

see http://twiki.di.uniroma1.it/twiki/view/Algoreti/ProgrammaLezioniDegliStudenti

---+++ <font color="blue" size="+3">Lesson Diary A.y. 2017-2018</font>

%BLUE%
*Friday September 29, 2017 (Lessons 1-2,5):*
%ENDCOLOR%

*Introduction*

*The Routing Problem i.e. the Shortest Path Problem (1)*
   * The routing Problem
   * The shortest path Problem (1)
      * shortest paths: BFS
      * the negative cycle issue
      * least cost paths: introduction

%BLUE%
*Monday October 2, 2017 (Lessons 2,5-5):*
%ENDCOLOR%

*The Routing Problem i.e. the Shortest Path Problem (2)*
   * The shortest path Problem (2)
      * least cost paths (cnt.d):
        * Bellman-Ford algorithm
         * Dijkstra algorithm
         * Floyd-Warshall algorithm
   * The Routing Problem on Interconnection Topologies (1)
      * 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
      * the Benes network

%BLUE%
*Friday October 6, 2017 (Lessons 5-7,5):*
%ENDCOLOR%

*The Routing Problem i.e. the Shortest Path Problem (3)*
   * The Routing Problem on Interconnection Topologies (2)
      * 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
   * Collinear Layout of the Complete network
   * Layout of the Complete network

%BLUE%
*Monday October 9, 2017 (lessons 7,5-10):*
%ENDCOLOR%

*The Problem of Laying out Interconnection Topologies i.e. the Grid Orthogonal Drawing Problem (2)*
   * Layout of the Butterfly network (1)
      * the Wise layout
      * the Even & Even layout
      * comparison between the two methods

%BLUE%
*Friday October 13, 2017 (lessons 10-12,5):*
%ENDCOLOR%

*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

%BLUE%
*Monday October 16, 2017 (lessons 12,5-15):*
%ENDCOLOR%

*The problem of worm propagation/prevention i.e. the Minimum Vertex Covering Problem*
   * 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 with vertex cover
      * another approximation algorithm
      * Konig-Egevary theorem

*The Problem of Minimizing Boolean Circuits i.e. the Minimum Set Covering Problem (1)*
   * The problem of minimizing boolean functions
   * Model of the problem on graphs: the Minimum Set Covering Problem
      * definition
      * ILP formulation
      * relation with the Minimum Vertex Covering Problem
      * an O(log n)-approximation algorithm

%BLUE%
*Friday October 20, 2017 (lessons 15-17,5):*
%ENDCOLOR%

*The Problem of Minimizing Boolean Circuits i.e. the Minimum Set Covering Problem (2)*
   * 
      * another approximation algorithm
      * some related problems
         * Hitting set problem
         * Edge Cover problem
         * Set Packing problem
         * Exact Cover 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
   * L(h,k)-labeling and minimum span
      * The special case h=k in relation to the suqre of a graph
      * Properties of the L(h,k)-labeling and their proofs

%BLUE%
*Monday October 23, 2017 (lessons 17.5-20):*
%ENDCOLOR%

*Student Lessons with the presence of the teacher (1)*

see http://twiki.di.uniroma1.it/twiki/view/Algoreti/ProgrammaLezioniDegliStudenti

%BLUE%
*Friday October 27, 2017 (lessons 20-22.5):*
%ENDCOLOR%

*A Frequency assignment problem i.e. the L(h,k)-Labeling Problem (2)*
   * 
      * Proof of NP-completeness for diameter 2 graphs
      * Lower bound of Delta+1 on lambbda
      * 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
      * Approximate results: outerplanar graphs

%BLUE%
*Monday October 30, 2017 (lessons 22.5-25):*
%ENDCOLOR%

*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
      * frequency assignment in GSM networks
   * 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)

%BLUE%
*Friday November 3, 2017 (lessons 25-27.5):*
%ENDCOLOR%
*The minimum energy broadcast i.e. the minimum spanning tree (2)*

   * The MST problem
      * Kruskal algorithm
      * Prim algorithm
      * Boruvka algorithm
   * the Min Broadcast broblem
      * MST euristic
      * SPT euristic
      * BAIP euristic
      * approximation ratio for SPT

%BLUE%
*Monday November 6, 2017 (lessons 27.5-30):*
%ENDCOLOR%
*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

%BLUE%
*Friday November 10, 2017 (lessons 30-32.5):*
%ENDCOLOR%

Attendance at the Workshop in honour of Janos Korner (both students and teacher)

%BLUE%
*Monday November 13, 2017 (lessons 32.5-35):*
%ENDCOLOR%

*Student Lessons with the presence of the teacher (2)*
see http://twiki.di.uniroma1.it/twiki/view/Algoreti/ProgrammaLezioniDegliStudenti

%BLUE%
*Friday November 17, 2017 (lessons 35-37.5):*
%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 a bipartite graphs
   * maximum matching in a bipartite graph
      * P. Hall theorem (with proof)
      * corollary to the P. Hall theorem
      * searching an augmenting path
      * Berge theorem on the augmenting paths
      * algorithm based on Berge theorem
      * Hopcroft & Karp algorithm

%BLUE%
*Monday November 20, 2017 (lessons 37.5-40):*
%ENDCOLOR%

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

   * Minimum weight perfect matching in bipartite graphs
      * 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)

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

   * The problem
   * A Possible Approach: Virtual Forces

*EVALUATION OF THE COURSE*

%BLUE%
*Friday November 24, 2017 (lessons 40-42.5):*
%ENDCOLOR%

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

   * A Protocol Based on Voronoi Diagrams
   * Voronoi Diagrams
      * hypthesis of general position
      * properties
      * complexity
      * the dual problem: Delaunay triangulation
   * Algorithms to compute the Voronoi diagram
      * half-plane intersection (divide et impera)
      * Fortune's algorithm

%BLUE%
*Monday November 27, 2017 (lessons 42.5-45):*
%ENDCOLOR%

*Student Lessons with the presence of the teacher (3)*
see http://twiki.di.uniroma1.it/twiki/view/Algoreti/ProgrammaLezioniDegliStudenti

%BLUE%
*Friday December 1, 2017 (lessons 45-47.5):*
%ENDCOLOR%

*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? (1)*

Some theses proposals

%BLUE%
*Monday December 4, 2017 (lessons 47.5-50):*
%ENDCOLOR%

IT Meeting - http://www.studiareinformatica.uniroma1.it/38-it-meeting-lunedi-4-dicembre-2017

%BLUE%
*Friday December 8, 2017:*
%ENDCOLOR%

*Holiday*

%BLUE%
*Monday December 11, 2017 (lessons 50-52.5):*
%ENDCOLOR%

*Monitoring by UAVs i.e. What? (2)*

Some theses proposals

*Some problems in (co-)Phylogeny*

Some other theses proposals

%BLUE%
*Friday December 15, 2017 (lessons 52.5-55):*
%ENDCOLOR%

*Student Lessons with the presence of the teacher (4)*
see http://twiki.di.uniroma1.it/twiki/view/Algoreti/ProgrammaLezioniDegliStudenti

%BLUE%
*Monday December 18, 2017 (lessons 55-57.5):*
%ENDCOLOR%

*Student Lessons with the presence of the teacher (5)*
see http://twiki.di.uniroma1.it/twiki/view/Algoreti/ProgrammaLezioniDegliStudenti

%BLUE%
*Friday December 22, 2017 (lessons 57.5-60):*
%ENDCOLOR%

*Mid term exam*

---+++ <font color="blue" size="+3">Previous years' Diaries</font>
---+++ <font color="blue" size="+2">Lesson Diary A.y. 2016-2017</font>

%BLUE%
*Monday September 26, 2016 (Lessons 1-2):*
%ENDCOLOR%

*Introduction*

*The Routing Problem i.e. the Shortest Path Problem (1)*
   * The routing Problem
   * The shortest path Problem (1)
      * shortest paths: BFS
      * the negative cycle issue
      * least cost paths: introduction
        * Bellman-Ford algorithm

%BLUE%
*Friday September 30, 2016 (Lessons 3-4):*
%ENDCOLOR%

*The Routing Problem i.e. the Shortest Path Problem (2)*
   * The shortest path Problem (2)
      * least cost paths (cnt.d):
         * Dijkstra algorithm
         * Floyd-Warshall algorithm
   * The Routing Problem on Interconnection Topologies (1)
      * the packet switching model
      * the Butterfly network

%BLUE%
*Monday October 3, 2016 (Lessons 5-6):*
%ENDCOLOR%

*The Routing Problem i.e. the Shortest Path Problem (3)*
   * The Routing Problem on Interconnection Topologies (2)
      * routing on the Butterfly network: the greedy algorithm
      * the concept of blocking network, non-blocking network and rearrangeable network
      * 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
   * Collinear Layout of the Complete network
   * Layout of the Complete network

%BLUE%
*Friday October 7, 2016 (lessons 7-8):*
%ENDCOLOR%

*The Problem of Laying out Interconnection Topologies i.e. the Grid Orthogonal Drawing Problem (2)*
   * Layout of the Butterfly network (1)
      * the Wise layout
      * the Even & Even layout
      * comparison between the two methods

%BLUE%
*Monday October 10, 2016 (lessons 9-10):*
%ENDCOLOR%

*The Problem of Laying out Interconnection Topologies i.e. the Grid Orthogonal Drawing Problem (3)*
   * Layout of the Butterfly network (2)
      * Optimal area Layout of the Butterfly
   * Layout of the Hypercube network
      * Collinear layout
      * general layout
   * The 3D layout problem

%BLUE%
*Friday October 14, 2016 (lessons 11-12):*
%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 with vertex cover
      * another approximation algorithm

%BLUE%
*Monday October 17, 2016 (lessons 13-14):*
%ENDCOLOR%

*The problem of worm propagation/prevention i.e. the Minimum Vertex Covering Problem (2)*
   * minimum vertex cover (cntd)
      * Konig-Egevary theorem
*The Problem of Minimizing Boolean Circuits i.e. the Minimum Set Covering Problem (1)*
   * The problem of minimizing boolean functions
   * Model of the problem on graphs: the Minimum Set Covering Problem
      * definition
      * ILP formulation
      * relation with the Minimum Vertex Covering Problem
      * an O(log n)-approximation algorithm
      * another approximation algorithm

%BLUE%
*Friday October 21, 2016 (lessons 15-16):*
%ENDCOLOR%

*The Problem of Minimizing Boolean Circuits i.e. the Minimum Set Covering Problem (2)*
   * 
      * some related problems
         * Hitting set problem
         * Edge Cover problem
         * Set Packing problem
         * Exact Cover 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

%BLUE%
*Monday October 24, 2016 (lessons 17-18):*
%ENDCOLOR%
*A Frequency assignment problem i.e. the L(h,k)-Labeling Problem (2)*
   * L(h,k)-labeling and minimum span
      * The special case h=k in relation to the suqre 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 lambbda
      * Exemple: a graph requiring lambda=Delta squared - Delta

%BLUE%
*Friday October 28, 2016 (lessons 19-20):*
%ENDCOLOR%
*A Frequency assignment problem i.e. the L(h,k)-Labeling Problem (3)*
   * L(h,k)-labeling and minimum span (cntd)
      * 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
      * Approximate results: outerplanar graphs (part)

%BLUE%
*Monday October 31, 2016 (lessons 21-22):*
%ENDCOLOR%
No lessons, due to security check after the earthquacke of October 30.

%BLUE%
*Friday November 4, 2016 (lessons 23-24):*
%ENDCOLOR%
*A Frequency assignment problem i.e. the L(h,k)-Labeling Problem (4)*
   * L(h,k)-labeling and minimum span (cntd)
       * Approximate results: outerplanar graphs (part)
   * variations of the problem:
      * oriented L(2,1)-labeling
      * L(h1, ..., hk)-labeling
      * backbone coloring
      * multiple L(h,k)-labeling
      * frequency assignment in GSM networks
   * a parenthesis on the 4 color theorem

%BLUE%
*Monday November 7, 2016 (lessons 25-26):*
%ENDCOLOR%
Mid term evaluation (part 1).

%BLUE%
*Friday November 11, 2016 (lessons 27-28):*
%ENDCOLOR%
Mid term evaluation (part 2).

%BLUE%
*Monday November 14, 2016 (lessons 29-30):*
%ENDCOLOR%
*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)

%BLUE%
*Friday November 18, 2016 (lessons 31-32):*
%ENDCOLOR%
*The minimum energy broadcast i.e. the minimum spanning tree (2)*

   * The MST problem
      * Kruskal algorithm
      * Prim algorithm
      * Boruvka algorithm
   * the Min Broadcast broblem
      * MST euristic
      * SPT euristic
      * BAIP euristic
      * approximation ratio for SPT

%BLUE%
*Monday November 21, 2016 (lessons 33-34):*
%ENDCOLOR%
*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

%BLUE%
*Friday November 25, 2016 (lessons 35-36):*
%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 a bipartite graphs
   * maximum matching in a bipartite graph
      * P. Hall theorem (with proof)
      * corollary to the P. Hall theorem
      * searching an augmenting path
      * Berge theorem on the augmenting paths

%BLUE%
*Monday November 28, 2016 (lessons 37-38):*
%ENDCOLOR%

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

   * 
      * algorithm based on Berge theorem
      * Hopcroft & Karp algorithm
   * Minimum weight perfect matching in bipartite graphs
      * 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)

%BLUE%
*Friday December 2, 2016 (lessons 39-40):*
%ENDCOLOR%

*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
      * hypthesis of general position
      * properties
      * complexity
      * the dual problem: Delaunay triangulation
   * Algorithms to compute the Voronoi diagram
      * half-plane intersection (divide et impera)

%BLUE%
*Monday December 5, 2016 (lessons 41-42):*
%ENDCOLOR%

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

   * Algorithms to compute the Voronoi diagram (cntd)
      * Fortune's algorithm
   * Heterogeneous sensors
   * A new notion of distance: Laguerre distance
   * Voronoi-Laguerre diagrams
   * A protocol based on Voronoi-Laguerre distance

%BLUE%
*Friday December 9, 2016 (lessons 43-44):*
%ENDCOLOR%
*No lesson: the building is closed*

%BLUE%
*Monday December 12, 2016 (lessons 45-46):*
%ENDCOLOR%
*Student lessons*

%BLUE%
*Friday December 16, 2016 (lessons 47-48):*
%ENDCOLOR%
*IT meeting*

%BLUE%
*Monday December 19, 2016 (lessons 49-50):*
%ENDCOLOR%
*Student lessons*

%BLUE%
*Tuesday December 20, 2016 (lessons 51-52):*
%ENDCOLOR%
*Student lessons*

---+++ <font color="blue" size="+2">Lesson Diary A.y. 2015-2016</font>

%BLUE%
*Tuesday September 22, 2015 (Lessons 1-2):*
%ENDCOLOR%

*Introduction*

*The Routing Problem i.e. the Shortest Path Problem (1)*
   * The routing Problem
   * The shortest path Problem (1)
      * shortest paths: BFS
      * the negative cycle issue
      * least cost paths: introduction

%BLUE%
*Friday September 25, 2015 (Lessons 3-4):*
%ENDCOLOR%

*The Routing Problem i.e. the Shortest Path Problem (2)*
   * The shortest path Problem (2)
      * least cost paths (cnt.d):
         * Bellman-Ford algorithm
         * Dijkstra algorithm
         * Floyd-Warshall algorithm
   * The Routing Problem on Interconnection Topologies (1)
      * the packet switching model
      * the Butterfly network
      * routing on the Butterfly network: the greedy algorithm

%BLUE%
*Tuesday September 29, 2015 (Lessons 5-6):*
%ENDCOLOR%

*The Routing Problem i.e. the Shortest Path Problem (3)*
   * The Routing Problem on Interconnection Topologies (2)
      * the concept of blocking network, non-blocking network and rearrangeable network
      * 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
   * Collinear Layout of the Complete network

%BLUE%
*Friday October 2, 2015 (lessons 7-8):*
%ENDCOLOR%

*The Problem of Laying out Interconnection Topologies i.e. the Grid Orthogonal Drawing Problem (2)*
   * Layout of the Complete network
   * Layout of the Butterfly network
      * the Wise layout

%BLUE%
*Friday October 2, 2015 (lessons 9-10):*
%ENDCOLOR%

*The Problem of Laying out Interconnection Topologies i.e. the Grid Orthogonal Drawing Problem (3)*
   * Layout of the Butterfly network (3)
      * the Even & Even layout
      * comparison between the two methods

%BLUE%
*Tuesday October 6, 2015 (lessons 11-12):*
%ENDCOLOR%

*The Problem of Laying out Interconnection Topologies i.e. the Grid Orthogonal Drawing Problem (4)*
   * Layout of the Butterfly network (4)
      * Optimal area Layout of the Butterfly
   * Layout of the Hypercube network
   * The 3D layout problem

%BLUE%
*Tuesday October 9, 2015 (lessons 13-14):*
%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 with vertex cover

%BLUE%
*Tuesday October 13, 2015 (lessons 15-16):*
%ENDCOLOR%

*The problem of worm propagation/prevention i.e. the Minimum Vertex Covering Problem (2)*
   * minimum vertex cover (cntd)
      * another approximation algorithm
      * Konig-Egevary theorem
*The Problem of Minimizing Boolean Circuits i.e. the Minimum Set Covering Problem*
   * The problem of minimizing boolean functions
   * Model of the problem on graphs: the Minimum Set Covering Problem
      * definition
      * ILP formulation
      * relation with the Minimum Vertex Covering Problem
      * an O(log n)-approximation algorithm
      * another approximation algorithm
      * some related problems
         * Hitting set problem
         * Edge Cover problem
         * Set Packing problem
         * Exact Cover problem

%BLUE%
*Tuesday October 20, 2015 (lessons 17-18):*
%ENDCOLOR%

*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
   * L(h,k)-labeling and minimum span
      * The special case h=k in relation to the suqre of a graph
      * Properties of the L(h,k)-labeling and their proofs
      * Proof of NP-completeness for diameter 2 graphs

%BLUE%
*Friday October 23, 2015 (lessons 19-20):*
%ENDCOLOR%

*A Frequency assignment problem i.e. the L(h,k)-Labeling Problem (2)*
   * L(h,k)-labeling and minimum span (cntd.)
      * Lower bound of Delta+1 on lambbda
      * Exemple: 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

%BLUE%
*Tuesday October 27, 2015 (lessons 21-22):*
%ENDCOLOR%

*A Frequency assignment problem i.e. the L(h,k)-Labeling Problem (3)*
   * L(h,k)-labeling and minimum span (cntd.)
      * Approximate results: outerplanar graphs
   * variations of the problem:
      * oriented L(2,1)-labeling
      * L(h1, ..., hk)-labeling
      * backbone coloring
      * multiple L(h,k)-labeling
      * frequency assignment in GSM networks
   * a parenthesis on the 4 color theorem

%BLUE%
*Friday October 30, 2015 (lessons 23-24):*
%ENDCOLOR%

*The minimum energy broadcast i.e. the minimum spanning tree (1)*
   * the MinBroadcast problem
   * NP-completeness and inapproximability results (reduction from MinSetCover)
   * Relation between MinBroadcast and MinSpanningTree

%BLUE%
*Friday November 6, 2015:*
%ENDCOLOR%

Mid term exam

%BLUE%
*Tuesday November 10, 2015 (lessons 25-26):*
%ENDCOLOR%

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

   * the Min Broadcast broblem
      * MST euristic
      * SPT euristic
      * BAIP euristic
      * approximation ratio for SPT

%BLUE%
*Friday November 13, 2015 (lessons 27-28):*
%ENDCOLOR%

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

   * the problem of centralized deployment
   * the problem on graphs: min weight matching in a bipartite graphs
   * maximum matching in a bipartite graph
      * P. Hall theorem (with proof)
      * corollary to the P. Hall theorem
      * searching an augmenting path
      * Berge theorem on the augmenting paths

%BLUE%
*Tuesday November 17, 2015 (lessons 29-30):*
%ENDCOLOR%

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

   * 
      * algorithm based on Berge theorem
      * Hopcroft & Karp algorithm
   * Minimum weight perfect matching in bipartite graphs
      * 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)

%BLUE%
*Friday November 20, 2015 (lessons 31-32):*
%ENDCOLOR%

*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
      * hypthesis of general position
      * properties
      * complexity
      * the dual problem: Delaunay triangulation
   * Algorithms to compute the Voronoi diagram
      * half-plane intersection (divide et impera)

%BLUE%
*Tuesday November 24, 2015 (lessons 33-34):*
%ENDCOLOR%

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

   * Algorithms to compute the Voronoi diagram (cntd)
      * Fortune's algorithm
   * Heterogeneous sensors
   * A new notion of distance: Laguerre distance
   * Voronoi-Laguerre diagrams
   * A protocol based on Voronoi-Laguerre distance

---+++ <font color="blue" size="+2">Lesson Diary A.y. 2014-2015</font>

%RED%
*Tuesday September 29, 2014 (Lessons 1-2):*
%ENDCOLOR%

*Introduction*

*The Routing Problem i.e. the Shortest Path Problem (1)*
   * The routing Problem
   * The shortest path Problem (1)
      * shortest paths: BFS
      * least cost paths: introduction

%RED%
*Friday October 3, 2014 (Lessons 3-4):*
%ENDCOLOR%

*The Routing Problem i.e. the Shortest Path Problem (2)*
   * The shortest path Problem (2)
      * least cost paths (cnt.d):
         * Bellman-Ford algorithm
         * Dijkstra algorithm
         * Floyd-Warshall algorithm
   * The Routing Problem on Interconnection Topologies (1)
      * the packet switching model
      * the Butterfly network
      * routing on the Butterfly network: the greedy algorithm

%RED%
*Tuesday October 7, 2014 (Lessons 5-6):*
%ENDCOLOR%

*The Routing Problem i.e. the Shortest Path Problem (3)*
   * The Routing Problem on Interconnection Topologies (2)
      * the concept of blocking network, non-blocking network and rearrangeable network
      * 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 Butterfly network (1)

%RED%
*Friday October 10, 2014 (lessons 7-8):*
%ENDCOLOR%

*The Problem of Laying out Interconnection Topologies i.e. the Grid Orthogonal Drawing Problem (2)*
   * Layout of the Butterfly network (2)
      * the Wise layout
      * the Even & Even layout
      * comparison between the two methods

%RED%
*Tuesday October 14, 2014 (lessons 9-10):*
%ENDCOLOR%

*The Problem of Laying out Interconnection Topologies i.e. the Grid Orthogonal Drawing Problem (3)*
   * Layout of the Butterfly network (3)
      * Optimal area Layout of the Butterfly
   * Layout of the Hypercube network
   * The 3D layout problem

%RED%
*Tuesday October 17, 2014 (lessons 11-12):*
%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 in relation with vertex cover

%RED%
*Tuesday October 21, 2014 (lessons 13-14):*
%ENDCOLOR%

*The problem of worm propagation/prevention i.e. the Minimum Vertex Covering Problem (2)*
   * minimum vertex cover (cnt.d)
      * matching in relation with vertex cover
      * another approximation algorithm
      * Konig-Egevary theorem
*The Problem of Minimizing Boolean Circuits i.e. the Minimum Set Covering Problem*
   * The problem of minimizing boolean functions
   * Model of the problem on graphs: the Minimum Set Covering Problem
      * definition
      * ILP formulation
      * relation with the Minimum Vertex Covering Problem
      * an O(log n)-approximation algorithm
      * another approximation algorithm
      * some related problems
         * Hitting set problem
         * Edge Cover problem
         * Set Packing problem
         * Exact Cover problem

%RED%
*Friday October 24, 2014:*
%ENDCOLOR%

*No lesson because of bus and train strike*

%RED%
*Tuesday October 28, 2014 (lessons 15-16):*
%ENDCOLOR%

*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
   * L(h,k)-labeling and minimum bandwidth
      * The special case h=k in relation to the suqre of a graph
      * Properties of the L(h,k)-labeling and their proofs

%RED%
*Friday October 31, 2014 (lessons 17-18):*
%ENDCOLOR%

*A Frequency assignment problem i.e. the L(h,k)-Labeling Problem (2)*
   * L(h,k)-labeling and minimum bandwidth (cntd.)
      * Proof of NP-completeness for diameter 2 graphs
      * Lower bound of Delta+1 on lambbda
      * Exemple: 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

%RED%
*Tuesday November 4, 2014 (lessons 19-20):*
%ENDCOLOR%

*A Frequency assignment problem i.e. the L(h,k)-Labeling Problem (3)*
   * L(h,k)-labeling and minimum bandwidth (cntd.)
      * Exact results: paths
      * Exact results: cycles
      * Approximate results: outerplanar graphs
   * variations of the problem:
      * oriented L(2,1)-labeling
      * L(h1, ..., hk)-labeling
      * backbone coloring
      * multiple L(h,k)-labeling

%RED%
*Friday November 7, 2014 (lessons 21-22):*
%ENDCOLOR%

Mid term exam

%RED%
*Tuesday November 11, 2014 (lessons 23-24):*
%ENDCOLOR%

*A Frequency assignment problem i.e. the L(h,k)-Labeling Problem (4)**
    variations of the problem (cnt.d):
   * 
      * frequency assignment in GSM networks
   * a parenthesis on the 4 color theorem
*The minimum energy broadcast i.e. the minimum spanning tree (1)*
   * the MinBroadcast problem
   * NP-completeness and inapproximability results (reduction from MinSetCover)
   * Relation between MinBroadcast and MinSpanningTree

%RED%
*Friday November 14, 2014 (lessons 25-26):*
%ENDCOLOR%

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

   * the Min Broadcast broblem
      * MST euristic
      * SPT euristic
      * BAIP euristic

%RED%
*Tuesday November 18, 2014 (lessons 27-28):*
%ENDCOLOR%

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

   * the Min Broadcast broblem (cnt.d)
      * approximation ratio for SPT

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

   * the problem of centralized deployment
   * Ithe problem on graphs: min weight matching in a bipartite graphs
   * maximum matching in a bipartite graph
      * P. Hall theorem (with proof)
      * corollary to the P. Hall theorem

%RED%
*Friday November 21, 2014 (lessons 29-30):*
%ENDCOLOR%

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

   * Maximum matching in bipartite graphs
      * searching an augmenting path
      * Berge theorem on the augmenting paths
      * algorithm based on Berge theorem
      * Hopcroft & Karp algorithm
   * Minimum weight perfect matching in bipartite graphs
      * 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)

%RED%
*Tuesday November 25, 2014 (lessons 31-32):*
%ENDCOLOR%

*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
      * hypthesis of general position
      * properties
      * complexity
      * the dual problem: Delaunay triangulation
   * Algorithms to compute the Voronoi diagram
      * half-plane intersection (divide et impera)

*Friday November 28, 2014 (lessons 33-34):*

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

   * Algorithms to compute the Voronoi diagram (cnt.d)
      * Fortune's algorithm
   * Heterogeneous sensors
   * A new notion of distance: Laguerre distance

%RED%
*Tuesday December 2, 2014 (lessons 35-36):*
%ENDCOLOR%

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

   * Voronoi-Laguerre diagrams
   * A protocol based on Voronoi-Laguerre distance

%RED%
*Friday December 5, 2014 (lessons 37-38):*
%ENDCOLOR%

*Student lessons (1)*

%RED%
*Tuesday December 9, 2014 (lessons 39-40):*
%ENDCOLOR%

*Student lessons (2)*

%RED%
*Tuesday December 16, 2014 (lessons 41-42):*
%ENDCOLOR%

*Student lessons (3)*

---++ <font color="blue" size="+2">Lesson Diary A.y. 2013-2014</font>

%RED%
*Monday September 30, 2013 (Lessons 1-2):*
%ENDCOLOR%

*Introduction*

*The Routing Problem i.e. the Shortest Path Problem (1)*

   * The routing Problem
   * The shortest path Problem (1)
      * shortest paths: BFS
      * least cost paths:
         * Bellman-Ford algorithm
         * Dijkstra algorithm

%RED%
*Friday October 4, 2013 (lessons 3-4):*
%ENDCOLOR%

*The Routing Problem i.e. the Shortest Path Problem (2)*

   * The shortest path Problem (2)
      * least cost paths (cntd.):
         * 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
      * the Benes network
      * routing om the Benes network: the looping algorithm

%RED%
*Monday October 7, 2013 (lessons 5-6):*
%ENDCOLOR%

*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 Butterfly network (1)
      * the Wise layout
      * the Even & Even layout

%RED%
*Friday October 11, 2013 (lessons 7-8):*
%ENDCOLOR%

*The Problem of Laying out Interconnection Topologies i.e. the Grid Orthogonal Drawing Problem (2)*
   * Layout of the Butterfly network (2)
      * Overview of other results
      * Optimal area Layout of the Butterfly
   * Layout of the Hypercube network
   * The 3D layut problem

%RED%
*Monday October 14, 2013 (lessons 9-10):*
%ENDCOLOR%

*The problem of worm propagation/prevention i.e. the Minimum Vertex Covering Problem (1)*
   * The problem
      * worms
      * damages caused by worms
      * worm expansion
   * Model of the problem on graphs
   * minimum vertex cover
      * definition
      * ILP model
      * a 2-approximation algorithm
      * independent set in relation with vertex cover
      * matching in relation with vertex cover
      * another approximation algorithm

%RED%
*Friday October 18, 2013 (lessons 11-12):*
%ENDCOLOR%

*The problem of worm propagation/prevention i.e. the Minimum Vertex Covering Problem (2)*
   * minimum vertex cover (cntd.)
      * Konig-Egevary theorem
*The Problem of Minimizing Boolean Circuits<span style="{encoded: 's1'};"> </span>i.e.<span style="{encoded: 's1'};"> </span>the Minimum<span style="{encoded: 's1'};"> </span>Set Covering Problem*
   * The problem of minimizing boolean functions
   * Its equivalence with the Minimum Set Covering Problem
   * the Minimum Set Covering Problem
      * definition
      * ILP formulation
      * relation with the Minimum Vertex Covering Problem
      * an O(log n)-approximation algorithm
      * another approximation algorithm
      * some related problems
         * Hitting set problem
         * Edge Cover problem
         * Set Packing problem
         * Exact Cover problem

%RED%
*Monday October 21, 2013 (lessons 13-14):*
%ENDCOLOR%

*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
   * L(h,k)-labeling and minimum bandwidth
      * The special case h=k in relation to the suqre of a graph
      * Properties of the L(h,k)-labeling and their proofs
      * Proof of NP-completeness for diameter 2 graphs

%RED%
*Friday October 25, 2013 (lessons 15-16):*
%ENDCOLOR%

*A Frequency assignment problem i.e. the L(h,k)-Labeling Problem (2)*
   * L(h,k)-labeling and minimum bandwidth (cntd.)
      * Lower bound of Delta+1 on lambbda
      * Exemple: 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

%RED%
*Monday October 28, 2013 (lessons 17-18):*
%ENDCOLOR%

*A Frequency assignment problem i.e. the L(h,k)-Labeling Problem (3)*
   * L(h,k)-labeling and minimum bandwidth (cntd.)
      * Approximate results: outerplanar graphs
   * variations of the problem:
      * oriented L(2,1)-labeling
      * L(h1, ..., hk)-labeling
      * backbone coloring
      * multiple L(h,k)-labeling
      * frequency assignment in GSM networks
   * a parenthesis on the 4 color theorem

%RED%
*Monday November 4, 2013 (lessons 19-20):*
%ENDCOLOR%

*The minimum energy broadcast i.e. the minimum spanning tree (1)*
   * the MinBroadcast problem
   * NP-completeness and inapproximability results (reduction from MinSetCover)
   * Relation between MinBroadcast and MinSpanningTree
   * the Minimum spanning tree problem
      * Kruskal algorithm
      * Prim algorithm
      * Boruvka algorithm

%RED%
*Friday November 8, 2013 (lessons 21-22):*
%ENDCOLOR%

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

   * the Min Broadcast broblem
      * MST euristic
      * SPT euristic
      * BAIP euristic
      * approximation ratio for SPT

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

   * the problem of centralized deployment
   * Ithe problem on graphs: min weight matching in a bipartite graphs
   * maximum matching in a bipartite graph
      * P. Hall theorem (with proof)
      * corollary to the P. Hall theorem

%BLUE%
*week November 11-15: No classes - midterm exams*
%ENDCOLOR%

%RED%
*Monday November 18, 2013 (lessons 23-24):*
%ENDCOLOR%

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

   * Maximum matching in bipartite graphs
      * searching an augmenting path
      * Berge theorem on the augmenting paths
      * algorithm based on Berge theorem
      * Hopcroft & Karp algorithm
   * Minimum weight perfect matching in bipartite graphs
      * augmenting paths
      * an algorithm based on searching augmenting paths
      * ILP formulation
   * Maximum matching in general graphs
      * blossoms
      * lemma on the cycle contraction
      * Edmonds algorithm

%RED%
*Friday November 22, 2013 (lessons 25-26):*
%ENDCOLOR%
*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
      * hypthesis of general position
      * properties
      * complexity
      * the dual problem: Delaunay triangulation
   * Algorithms to compute the Voronoi diagram
      * half-plane intersection (divide et impera)

%RED%
*Monday December 2, 2013 (lessons 27-28):*
%ENDCOLOR%
*The Distributed Deployment of Sensors i.e. the Construction of a Voronoi Diagram (2)*

   * Algorithms to compute the Voronoi diagram (cnt.d)
      * Fortune's algorithm

%RED%
*Friday December 6, 2013 (lessons 29-30):*
%ENDCOLOR%
*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 Voroi-Laguerre distance

%RED%
*Monday December 9, 2013 (lessons 31-32):*
%ENDCOLOR%

Student Lessons

%RED%
*Friday December 13, 2013 (lessons 33-34):*
%ENDCOLOR%

Student Lessons

%RED%
*Monday December 16, 2013 (lessons 35-36):*
%ENDCOLOR%

Student Lessons

---++ <font color="blue" size="+2">Diario delle Lezioni A.A. 2012-2013</font>

%RED%
*Mercoledi' 3 Ottobre 2011 (Ore 1-2):*
%ENDCOLOR%

*Introduzione al Corso*

*Il Problema dell'Instradamento<span style="{encoded: 's1'};"> </span>ovvero<span style="{encoded: 's1'};"> </span>il Cammino più Corto o di Costo minimo (1)*

   * Il problema dell'instradamento
   * Il problema del cammino di costo minimo
      * cammini piu' corti: visita in ampiezza
      * cammini minimi:
         * algoritmo di Bellman-Ford

%RED%
*Lunedi' 8 Ottobre 2012 (Ore 3-4):*
%ENDCOLOR%

*Il Problema dell'Instradamento ovvero il Cammino più Corto o di Costo minimo (2)*

   * 
      * cammini minimi (segue):
         * algoritmo di Dijkstra
         * algoritmo di Floyd-Warshall

   * Instradamento sulle Topologie di Interconnessione
      * il modello di packet switching
      * la Butterfly
      * instradamento sulla Butterfly

%RED%
*Mercoledi' 10 Ottobre 2012 (Ore 5-6):*
%ENDCOLOR%

*Il Problema dell'Instradamento<span style="{encoded: 's1'};"> </span>ovvero<span style="{encoded: 's1'};"> </span>il Cammino più Corto o di Costo minimo (3)*
   * 
      * concetto di rete bloccante, di rete non bloccante e di rete riarrangabile
      * la Benes
      * looping algorithm e instradamento sulla Benes

*Il Problema del Layout di Topologie di Interconnessione ovvero il Disegno Ortogonale su Griglia (1)*
   * Il modello di Thompson
   * Il disegno ortogonale di grafi su griglia
   * Il layout della Butterfly
      * il layout di Wise

%RED%
*Lunedi' 15 Ottobre 2012 (Ore 7-8):*
%ENDCOLOR%

*Il Problema del Layout di Topologie di Interconnessione ovvero il Disegno Ortogonale su Griglia (2)*
   * Il layout della Butterfly (segue)
      * il layout di Even ed Even
      * panoramica di altri risultati
      * Layout della butterfly di area ottima

%RED%
*Mercoledi' 17 Ottobre 2012 (Ore 9-10):*
%ENDCOLOR%

*Il Problema del Layout di Topologie di Interconnessione ovvero il Disegno Ortogonale su Griglia (3)*
   * Il layout dell'ipercubo
   * il problema del layut 3D

*Il Problema di infettare (e difendere) una rete con un Worm ovvero la Minima Copertura di Nodi (1)*
   * Il problema
      * i worm
      * danni causati dai worm
      * diffusione dei worm

%RED%
*Lunedi' 22 Ottobre 2012 (Ore 11-12):*
%ENDCOLOR%

*Il Problema di infettare (e difendere) una rete con un Worm ovvero la Minima Copertura di Nodi (2)*
   * Modello del problema su grafi
   * la minima copertura di nodi
      * definizione
      * un algoritmo 2-approssimante
      * insieme indipendente e sua relazione con la copertura di nodi
      * accoppiamento e sua relazione con la copertura di nodi
      * un ulteriore algoritmo approssimante
      * teorema di Konig-Egevary

%RED%
*Mercoledi' 24 Ottobre 2012 (Ore 13-14):*
%ENDCOLOR%

*Un Problema di assegnazione di frequenze ovvero la L(h,k)-Etichettatura (1)*
   * Introduzione ai problemi di assegnazione di frequenze
   * Collisioni dirette, collisioni nascoste e grafo delle interferenze
   * L(h,k)-etichettatura e minima banda
      * Il caso speciale h=k in relazione al quadrato di un grafo

%RED%
*Lunedi' 29 Ottobre 2012 (Ore 15-16):*
%ENDCOLOR%

*Un Problema di assegnazione di frequenze ovvero la L(h,k)-Etichettatura (2)*
   * L(h,k)-etichettatura (segue)
      * Dimostrazione delle proprietà della L(h,k)-etichettatura (h e k primi tra loro ed interi)
      * Dimostrazione della NP-completezza per grafi di diametro 2
      * Limitazione inferiore di Delta+1 su lambbda
      * Esempio di grafo che richiede lambda=Delta quadro - Delta
      * Limitazione superiore di Delta quadro + 2 Delta
      * Congettura di Griggs e Yeh
      * Risultati esatti: clicche

%RED%
*Lunedi' 5 Novembre 2012 (Ore 17-18):*
%ENDCOLOR%

*Un Problema di assegnazione di frequenze ovvero la L(h,k)-Etichettatura (3)*
   * L(h,k)-etichettatura (segue)
      * Risultati esatti: clicche
      * Risultati esatti: stelle
      * Risultati esatti: alberi
      * Risultati esatti: cammini
      * Risultati esatti: cicli

%RED%
*Mercoledi' 7 Novembre 2012 (Ore 19-20):*
%ENDCOLOR%
*Un Problema di assegnazione di frequenze ovvero la L(h,k)-Etichettatura (4)*
   * L(h,k)-etichettatura (segue)

   * 
      * Risultati approssimati: grafi outerplanar
   * varianti del problema:
      * L(2,1)-etichettatura orientata
      * L(h1, ..., hk)-etichettatura
      * backbone coloring
      * L(h,k)-etichettatura multipla
      * assegnazione di frequenze in reti GSM
   * una divagazione sul teorema dei 4 colori

*Il Problema del Broadcast con minimo dispendio di energia ovvero il Minimo Albero Ricoprente (1)*
   * Il problema del MinBroadcast
   * NP-completezza e risultati di non approssimabilita' di MinBroadcast (riduzione da MinSetCover)

%RED%
*12-15 Novembre 2012: settimana di interruzione della didattica*
%ENDCOLOR%

%RED%
*Lunedi' 19 Novembre 2012 (Ore 21-22):*
%ENDCOLOR%
*Il Problema del Broadcast con minimo dispendio di energia ovvero il Minimo Albero Ricoprente (2)*
   * Relazione tra MinBroadcast e MinSpanningTree
   * Il problema del Minimo Albero Ricoprente
      * Algoritmo di Kruskal
      * Algoritmo di Prim
      * Algoritmo di Boruvka
   * Il problema del Min Broadcast
      * Euristica MST
      * Euristica SPT
      * Euristica BAIP
      * fattore di approssimazione per SPT

%RED%
*Mercoledi' 21 Novembre 2012 (Ore 23-24):*
%ENDCOLOR%

*Il Problema del Dispiegamento centralizzato di Sensori Mobili ovvero il Minimo Accoppiamento Bipartito (1)*

   * Il problema del Dispiegamento centralizzato
   * Il problema modellato sui grafi: accoppiamento bipartito di peso minimo
   * Accoppiamento massimo in grafi bipartiti
      * teorema di P. Hall (dimostrazione)
      * corollario del th. di P. Hall (dim.)
      * equivalenza con il problema del minimo flusso
      * cammini aumentanti

%RED%
*Lunedi' 26 Novembre 2012 (Ore 25-26):*
%ENDCOLOR%

*Il Problema del Dispiegamento Centralizzato di Sensori Mobili ovvero il Minimo Accoppiamento Bipartito (2)*

   * Accoppiamento massimo in grafi bipartiti
      * teorema del cammino aumentante di Berge (dim.)
      * il problema della ricerca di un camino aumentante
      * algoritmo basato sul th. di Berge
      * l'algoritmo di Hopcroft e Karp
   * Accoppiamento perfetto di peso minimo in grafi bipartiti
      * cammini aumentanti
      * un algoritmo basato sui cammini aumentanti
      * formulazione del problema come programmazione lineare
   * Accoppiamento massimo in grafi qualunque
      * boccioli (blossoms)
      * lemma della contrazione dei cicli

%RED%
*Mercoledi' 28 Novembre 2012 (Ore 27-28):*
%ENDCOLOR%

*Il Problema del Dispiegamento Centralizzato di Sensori Mobili ovvero il Minimo Accoppiamento Bipartito (3)*

   * 
      * algoritmo di Edmonds

*Il Problema del Dispiegamento distribuito di Sensori Mobili ovvero la costruzione del Diagramma di Voronoi (2)*

   * Il problema
   * L'approccio basato sulle forze virtuali

%RED%
*Lunedi' 3 Dicembre 2012 (Ore 29-30):*
%ENDCOLOR%

*Il Problema del Dispiegamento distribuito di Sensori Mobili ovvero la costruzione del Diagramma di Voronoi (2)*

   * L'approccio basato sui diagrammi di Voronoi
   * Diagramma di Voronoi
      * posizione generale
      * proprieta'

   * Diagramma di Voronoi
      * complessita'
      * Il problema duale: la triangolazione di Delaunay
      * algoritmi per calcolare il diagramma di Voronoi: divide et impera
      * algoritmi per calcolare il diagramma di Voronoi: sweep line (algoritmo di Fortune) - prima parte

%RED%
*Mercoledi' 5 Dicembre 2012 (Ore 31-32):*
%ENDCOLOR%

*Il Problema del Dispiegamento distribuito di Sensori Mobili ovvero la costruzione del Diagramma di Voronoi (3)*

   * Diagramma di Voronoi
      * algoritmi per calcolare il diagramma di Voronoi: sweep line (algoritmo di Fortune) - seconda parte

   * Dispiegamento con sensori eterogenei
   * Distanza di Laguerre
   * Diagramma di Voronoi-Laguerre
   * L'approccio basato sui diagrammi di Voronoi-Laguerre
      * proprieta' dell'algoritmo

---+++ <font color="blue" size="+2">Diario delle Lezioni A.A. 2011-2012</font>

%RED%
*Lunedi' 3 Ottobre 2011 (Ore 1-2):*
%ENDCOLOR%

*Introduzione al Corso*

*Il Problema dell'Instradamento<span style="{encoded: 's1'};"> </span>ovvero<span style="{encoded: 's1'};"> </span>il Cammino più Corto o di Costo minimo (1)*

   * Il problema dell'instradamento
   * Il problema del cammino di costo minimo
      * cammini piu' corti: visita in ampiezza

%RED%
*Giovedi' 6 Ottobre 2011 (Ore 3-4):*
%ENDCOLOR%

*Il Problema dell'Instradamento ovvero il Cammino più Corto o di Costo minimo (2)*

   * 
      * cammini minimi:
         * algoritmo di Bellman-Ford
         * algoritmo di Dijkstra
         * algoritmo di Floyd-Warshall

   * Instradamento sulle Topologie di Interconnessione
      * il modello di packet switching
      * la Butterfly
      * instradamento sulla Butterfly

%RED%
*Lunedi' 10 Ottobre 2011 (Ore 5-6):*
%ENDCOLOR%

*Il Problema dell'Instradamento<span style="{encoded: 's1'};"> </span>ovvero<span style="{encoded: 's1'};"> </span>il Cammino più Corto o di Costo minimo (3)*
   * 
      * concetto di rete bloccante, di rete non bloccante e di rete riarrangabile
      * la Benes
      * looping algorithm e instradamento sulla Benes

*Il Problema del Layout di Topologie di Interconnessione ovvero il Disegno Ortogonale su Griglia (1)*
   * Il modello di Thompson
   * Il disegno ortogonale di grafi su griglia

%RED%
*Mercoledi' 12 Ottobre 2011 (Ore 7-8):*
%ENDCOLOR%

*Il Problema del Layout di Topologie di Interconnessione ovvero il Disegno Ortogonale su Griglia (2)*
   * Il layout della Butterfly
      * il layout di Wise
      * il layout di Even ed Even
      * panoramica di altri risultati

%RED%
*Lunedi' 17 Ottobre 2011 (Ore 9-10):*
%ENDCOLOR%

*Il Problema del Layout di Topologie di Interconnessione ovvero il Disegno Ortogonale su Griglia (3)*
   * Layout della butterfly di area ottima
   * Layout tridimensionale dell'ipercubo
      * il problema del layut 3D
      * l'ipercubo
      * cenni sul layout dell'ipercubo e sulla limitazione inferiore

%RED%
*Mercoledi' 19 Ottobre 2011 (Ore 11-12):*
%ENDCOLOR%

*Il Problema di infettare (e difendere) una rete con un Worm ovvero la Minima Copertura di Nodi*
   * Il problema
      * i worm
      * danni causati dai worm
      * diffusione dei worm
   * Modello del problema su grafi
   * la minima copertura di nodi
      * definizione
      * un algoritmo 2-approssimante
      * insieme indipendente e sua relazione con la copertura di nodi
      * accoppiamento e sua relazione con la copertura di nodi
      * un ulteriore algoritmo approssimante
      * teorema di Konig-Egevary

%RED%
*Lunedi' 24 Ottobre 2011 (Ore 13-14):*
%ENDCOLOR%

*Un Problema di assegnazione di frequenze ovvero la L(h,k)-Etichettatura (1)*
   * Introduzione ai problemi di assegnazione di frequenze
   * Collisioni dirette, collisioni nascoste e grafo delle interferenze
   * L(h,k)-etichettatura e minima banda
      * Il caso speciale h=k in relazione al quadrato di un grafo
      * Dimostrazione delle proprietà della L(h,k)-etichettatura (h e k primi tra loro ed interi)

%RED%
*Mercoledi' 26 Ottobre 2011 (Ore 15-16):*
%ENDCOLOR%

*Un Problema di assegnazione di frequenze ovvero la L(h,k)-Etichettatura (2)*
   * L(h,k)-etichettatura (segue)
      * Dimostrazione della NP-completezza per grafi di diametro 2
      * Limitazione inferiore di Delta+1 su lambbda
      * Esempio di grafo che richiede lambda=Delta quadro - Delta
      * Limitazione superiore di Delta quadro + 2 Delta
      * Congettura di Griggs e Yeh
      * Risultati esatti: clicche
      * Risultati esatti: stelle
      * Risultati esatti: alberi

%RED%
*Mercoledi' 9 Novembre 2011 (Ore 17-18):*
%ENDCOLOR%

*Un Problema di assegnazione di frequenze ovvero la L(h,k)-Etichettatura (3)*
   * L(h,k)-etichettatura (segue)
      * Risultati esatti: cammini
      * Risultati esatti: cicli
      * Risultati approssimati: grafi outerplanar

%RED%
*Lunedi' 21 Novembre 2011 (Ore 19-20):*
%ENDCOLOR%

*Un Problema di assegnazione di frequenze ovvero la L(h,k)-Etichettatura (4)**
  varianti del problema:
   * 
      * L(2,1)-etichettatura orientata
      * L(h1, ..., hk)-etichettatura
      * backbone coloring
      * L(h,k)-etichettatura multipla
      * assegnazione di frequenze in reti GSM
   * una divagazione sul teorema dei 4 colori

*Il Problema del Broadcast con minimo dispendio di energia ovvero il Minimo Albero Ricoprente (1)*
   * Il problema del MinBroadcast
   * NP-completezza e risultati di non approssimabilita' di MinBroadcast (riduzione da MinSetCover)
   * Relazione tra MinBroadcast e MinSpanningTree

%RED%
*Mercoledi' 23 Novembre 2011 (Ore 21-22):*
%ENDCOLOR%
*Il Problema del Broadcast con minimo dispendio di energia ovvero il Minimo Albero Ricoprente (2)*
   * Il problema del Minimo Albero Ricoprente
      * Algoritmo di Kruskal
      * Algoritmo di Prim
      * Algoritmo di Boruvka
   * Il problema del Min Broadcast
      * Euristica MST
      * Euristica SPT
      * Euristica BAIP
      * fattore di approssimazione per SPT

%RED%
*Lunedi' 28 Novembre 2010 (Ore 23-24):*
%ENDCOLOR%

*Il Problema del Dispiegamento centralizzato di Sensori Mobili ovvero il Minimo Accoppiamento Bipartito (1)*

   * Il problema del Dispiegamento centralizzato
   * Il problema modellato sui grafi: accoppiamento bipartito di peso minimo
   * Accoppiamento massimo in grafi bipartiti
      * teorema di P. Hall (dimostrazione)
      * corollario del th. di P. Hall (dim.)
      * equivalenza con il problema del minimo flusso
      * cammini aumentanti
      * teorema del cammino aumentante di Berge (dim.)

%RED%
*Mercoledi' 30 Novembre 2010 (Ore 25-26):*
%ENDCOLOR%

*Il Problema del Dispiegamento centralizzato di Sensori Mobili ovvero il Minimo Accoppiamento Bipartito (2)*

   * Accoppiamento massimo in grafi bipartiti
      * il problema della ricerca di un camino aumentante
      * algoritmo basato sul th. di Berge
      * l'algoritmo di Hopcroft e Karp
   * Accoppiamento perfetto di peso minimo in grafi bipartiti
      * cammini aumentanti
      * un algoritmo basato sui cammini aumentanti
      * formulazione del problema come programmazione Lineare
   * Accoppiamento massimo in grafi qualunque
      * boccioli (blossoms)
      * lemma della contrazione dei cicli
      * algoritmo di Edmonds

%RED%
*Lunedi' 5 Dicembre 2011 (Ore 27-28):*
%ENDCOLOR%

*Il Problema del Dispiegamento distribuito di Sensori Mobili ovvero la costruzione del Diagramma di Voronoi (1)*

   * Il problema
   * L'approccio basato sulle forze virtuali
   * L'approccio basato sui diagrammi di Voronoi
   * Diagramma di Voronoi
      * posizione generale
      * proprieta'

%RED%
*Mercoledi' 7 Dicembre 2011 (Ore 29-30):*
%ENDCOLOR%

*Il Problema del Dispiegamento distribuito di Sensori Mobili ovvero la costruzione del Diagramma di Voronoi (2)*

   * Diagramma di Voronoi
      * complessita'
      * Il problema duale: la triangolazione di Delaunay
      * algoritmi per calcolare il diagramma di Voronoi: divide et impera
      * algoritmi per calcolare il diagramma di Voronoi: sweep line (algoritmo di Fortune)

   * Dispiegamento con sensori eterogenei
   * Distanza di Laguerre
   * Diagramma di Voronoi-Laguerre

%RED%
*Lunedi' 12 Dicembre 2011 (Ore 31-32):*
%ENDCOLOR%

*Il Problema del Dispiegamento distribuito di Sensori Mobili ovvero la costruzione del Diagramma di Voronoi (3)*

   * L'approccio basato sui diagrammi di Voronoi-Laguerre
      * proprieta' dell'algoritmo

%BLUE%
*Mercoledi' 14 Dicembre 2011 (Lauree)*
%ENDCOLOR%

%BLUE%
*Vacanze natalizie*
%ENDCOLOR%

%RED%
*Mercoledi' 11 Gennaio 2012 (Ore 33-34):*
%ENDCOLOR%

*Tesine*

%RED%
*Lunedi' 16 Gennaio 2012 (Ore 35-36):*
%ENDCOLOR%

*Tesine*

%RED%
*Mercoledi' 18 Gennaio 2012 (Ore 37-38):*
%ENDCOLOR%

*Tesine*
---

---+++ <font color="blue" size="+2">Diario delle Lezioni A.A. 2010-2011</font>

%RED%
*Lunedi' 18 Ottobre 2010 (Ore 1-2):*
%ENDCOLOR%

Lectio Magistralis: Dott. Prabhakar Raghavan

%RED%
*Giovedi' 21 Ottobre 2010 (Ore 3-4):*
%ENDCOLOR%

*Introduzione al Corso*

*Il Problema dell'Instradamento ovvero il Cammino più Corto o di Costo minimo (1)*

   * Il problema dell'instradamento
   * Il problema del cammino di costo minimo
      * cammini piu' corti: visita in ampiezza
      * cammini minimi:
         * algoritmo di Bellman-Ford
         * algoritmo di Dijkstra
         * algoritmo di Floyd-Warshall

%RED%
*Lunedi' 25 Ottobre 2010 (Ore 5-6):*
%ENDCOLOR%

*Il Problema dell'Instradamento ovvero il Cammino più Corto o di Costo minimo (2)*

   * Instradamento sulle Topologie di Interconnessione
      * il modello di packet switching
      * la Butterfly
      * instradamento sulla Butterfly
      * concetto di rete bloccante, di rete non bloccante e di rete riarrangabile
      * la Benes
      * looping algorithm e instradamento sulla Benes

%RED%
*Giovedi' 28 Ottobre 2010 (Ore 7-8):*
%ENDCOLOR%

*Il Problema del Layout di Topologie di Interconnessione ovvero il Disegno Ortogonale su Griglia (1)*
   * Il modello di Thompson
   * Il disegno ortogonale di grafi su griglia
   * Il layout della Butterfly
      * il layout di Wise
      * il layout di Even ed Even
      * panoramica di altri risultati

%BLUE%
*Lunedi' 1 Novembre 2010:* festa
%ENDCOLOR%

%RED%
*Giovedi' 4 Novembre 2010 (Ore 9-10):*
%ENDCOLOR%

*Il Problema del Layout di Topologie di Interconnessione ovvero il Disegno Ortogonale su Griglia (2)*
   * Layout della butterfly di area ottima
   * Layout tridimensionale dell'ipercubo
      * il problema del layut 3D
      * l'ipercubo
      * cenni sul layout e sulla limitazione inferiore

*Il Problema di infettare (e difendere) una rete con un Worm ovvero la Minima Copertura di Vertici (1)*
   * Il problema
      * i worm
      * danni causati dai worm
      * diffusione dei worm

%RED%
*Lunedi' 8 Novembre 2010 (Ore 11-12):*
%ENDCOLOR%

*Il Problema di infettare (e difendere) una rete con un Worm ovvero la Minima Copertura di Nodi (2)*
   * Modello del problema su grafi
   * la minima copertura di nodi
      * definizione
      * un algoritmo 2-approssimante
      * insieme indipendente e sua relazione con la copertura di nodi
      * accoppiamento e sua relazione con la copertura di nodi
      * un ulteriore algoritmo approssimante
      * teorema di Konig-Egevary

*Un Problema di assegnazione di frequenze ovvero la L(h,k)-Etichettatura (1)*
   * Introduzione ai problemi di assegnazione di frequenze

%RED%
*Giovedi' 11 Novembre 2010 (Ore 13-14):*
%ENDCOLOR%

*Un Problema di assegnazione di frequenze ovvero la L(h,k)-Etichettatura (2)*
   * Collisioni dirette, colisioni nascoste e grafo delle interferenze
   * L(h,k)-etichettatura e minima banda
      * Dimostrazione delle proprietà della L(h,k)-etichettatura (h e k primi tra loro ed interi)
      * Il caso speciale h=k
      * Dimostrazione della NP-completezza per grafi di diametro 2
      * Limitazione inferiore di Delta+1 su lambbda
      * Esempio di grafo che richiede lambda=Delta quadro - Delta
      * Limitazione superiore di Delta quadro + 2 Delta

%RED%
*Lunedi' 15 Novembre 2010 (Ore 15-16):*
%ENDCOLOR%

*Un Problema di assegnazione di frequenze ovvero la L(h,k)-Etichettatura (3)*
   * L(h,k)-etichettatura (segue)
      * Congettura di Griggs e Yeh
      * Risultati esatti: clicche
      * Risultati esatti: stelle
      * Risultati esatti: alberi
      * Risultati esatti: cammini
      * Risultati esatti: cicli
      * Risultati approssimati: grafi outerplanar

%RED%
*Giovedi' 18 Novembre 2010 (Ore 17-18):*
%ENDCOLOR%

*Un Problema di assegnazione di frequenze ovvero la L(h,k)-Etichettatura (4)**
  L(h,k)-etichettatura (segue)
   * 
      * Risultati approssimati: grafi outerplanar
   * varianti del problema:
      * L(2,1)-etichettatura orientata
      * L(h1, ..., hk)-etichettatura
      * backbone coloring
      * assegnazione di frequenze in reti GSM
      * una divagazione sul teorema dei 4 colori

%RED%
*Lunedi' 22 Novembre 2010 (Ore 19-20):*
%ENDCOLOR%

*Il Problema del Broadcast con minimo dispendio di energia ovvero il Minimo Albero Ricoprente (1)*
   * Il problema del MinBroadcast
   * NP-completezza e risultati di non approssimabilita' di MinBroadcast (riduzione da MinSetCover)
   * Relazione tra MinBroadcast e MinSpanningTree
   * Il problema del Minimo Albero Ricoprente
      * Algoritmo di Kruskal
      * Algoritmo di Prim
      * Algoritmo di Boruvka
   * Il problema del Min Broadcast
      * Euristica MST
      * Euristica SPT
      * Euristica BAIP
      * fattore di approssimazione per SPT

%RED%
*Giovedi' 25 Novembre 2010 (Ore 21-22):*
%ENDCOLOR%

*Il Problema del Broadcast con minimo dispendio di energia ovvero il Minimo Albero Ricoprente (2)*

   * Il problema del Min Broadcast
      * fattore di approssimazione per BAIP
      * fattore di approssimazione per MST
      * idea della dimostrazione della lim. sup. di 6 per MST

*Il Problema del Dispiegamento centralizzato di Sensori Mobili ovvero il Minimo Accoppiamento Bipartito (1)*

   * Il problema del Dispiegamento centralizzato
   * Il problema modellato sui grafi: accoppiamento bipartito di peso minimo
   * Accoppiamento massimo in grafi bipartiti
      * teorema di P. Hall (dimostrazione)
      * corollario del th. di P. Hall (dim.)
      * equivalenza con il problema del minimo flusso
      * cammini aumentanti
      * teorema del cammino aumentante di Berge (dim.)
      * il problema della ricerca di un camino aumentante
      * algoritmo basato sul th. di Berge
      * l'algoritmo di Hopcroft e Karp

%BLUE%
*Settimana di interruzione della didattica*
%ENDCOLOR%

%RED%
*Lunedi' 6 Dicembre 2010 (Ore 23-24):*
%ENDCOLOR%

*Il Problema del Dispiegamento centralizzato di Sensori Mobili ovvero il Minimo Accoppiamento Bipartito (2)*

   * Accoppiamento perfetto di peso minimo in grafi bipartiti
      * cammini aumentanti
      * un algoritmo basato sui cammini aumentanti
      * formulazione del problema come programmazione Lineare
   * Accoppiamento massimo in grafi qualunque
      * boccioli (blossoms)
      * lemma della contrazione dei cicli
      * algoritmo di Edmonds

*Il Problema del Dispiegamento distribuito di Sensori Mobili ovvero la costruzione del Diagramma di Voronoi (1)*

   * Il problema
   * L'approccio basato sulle forze virtuali
   * L'approccio basato sui diagrammi di Voronoi
   * Diagramma di Voronoi
      * posizione generale
      * proprieta'

%RED%
*Giovedi' 9 Dicembre 2010 (Ore 25-26):*
%ENDCOLOR%

*Il Problema del Dispiegamento distribuito di Sensori Mobili ovvero la costruzione del Diagramma di Voronoi (2)*

   * Diagramma di Voronoi
      * complessita'
      * Il problema duale: la triangolazione di Delaunay
      * algoritmi per calcolare il diagramma di Voronoi: divide et impera
      * algoritmi per calcolare il diagramma di Voronoi: sweep line (algoritmo di Fortune)

%RED%
*Lunedi' 13 Dicembre 2010 (Ore 27-28):*
%ENDCOLOR%

*Il Problema del Dispiegamento distribuito di Sensori Mobili ovvero la costruzione del Diagramma di Voronoi (3)*

   * Dispiegamento con sensori eterogenei
   * Distanza di Laguerre
   * Diagramma di Voronoi-Laguerre
   * L'approccio basato sui diagrammi di Voronoi-Laguerre
      * proprieta' dell'algoritmo

%BLUE%
*Giovedi' 16 Dicembre 2010 (Lauree)*
%ENDCOLOR%

%BLUE%
*Lunedi' 20 Dicembre 2010 (Incontro con le aziende)*
%ENDCOLOR%

%BLUE%
*Vacanze natalizie*
%ENDCOLOR%

%RED%
*Lunedi' 10 Gennaio 2011 (Ore 29-30):*
%ENDCOLOR%

*Tesine*

%RED%
*Giovedi' 13 Gennaio 2011 (Ore 31-32):*
%ENDCOLOR%

*Tesine*

%RED%
*Venerdi' 14 Gennaio 2011 (Ore 33-34):*
%ENDCOLOR%

*Tesine*

%RED%
*Lunedi' 17 Gennaio 2011 (Ore 35-36):*
%ENDCOLOR%

*Tesine*

%RED%
*Giovedi' 20 Gennaio 2011 (Ore 37-38):*
%ENDCOLOR%

*Tesine*

-- %USERSIG{TizianaCalamoneri - 2021-09-23}%

---++ Comments

%COMMENT%
This topic: Algoreti > WebHome1011 > DiarioDelleLezioni > PreviousYears
Topic revision: r4 - 2024-09-04 - TizianaCalamoneri