DiarioDelleLezioni < Algoreti

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


%GREEN% *Monday, September 23, 2024 (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
      * a parenthesis on the Connected Components Problem and its applications
   * The least cost path Problem (1)
      * the negative cycle issue and its applications
      * least cost paths: introduction
      * Bellman-Ford algorithm

%GREEN% *Thursday, September 26, 2024 (Lessons 4-5):* %ENDCOLOR%

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

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


%GREEN% *Monday, September 30, 2024 (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

%GREEN% *Thursday, October 3, 2024 (Lessons 9-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
      * The Wise layout

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

%GREEN% *Monday, October 7, 2024 (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

%RED% *Thursday, October 10, 2024:* %ENDCOLOR%
*NO LESSON*

%GREEN% *Monday October 14, 2024 (Lessons 14-15-16):* %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
   * 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

%GREEN% *Thursday, October 17, 2024 (Lessons 17-18):* %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 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% *Monday, October 21, 2024 (Lessons 19-20-21):* %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 24, 2024 (Lessons 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 MST


%RED% *Monday, October 28, 2024 (Lessons 24-25-26):* %ENDCOLOR%

*FIRST MID-TERM EXAM*


%GREEN% *Thursday, October 31, 2024 (Lessons 27-28):* %ENDCOLOR%

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



%GREEN% *Monday, November 4, 2024 (Lessons 29-30-31):* %ENDCOLOR%

*The data mule problem i.e. the TSP (1)*
   * (Fixed) sensor networks
   * The Data Mule problem
   * The TSP
      * NP-completeness
      * inapproximability
      * special cases: metric TSP and Euclidean TSP


%GREEN% *Thursday, November 7, 2024 (Lessons 32-33):* %ENDCOLOR%

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

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



%GREEN% *Monday, November 11, 2024 (Lessons 34-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 bipartite graphs
   * maximum matching in a bipartite graph (1)
      * P. Hall theorem (with proof)
      * corollary to the P. Hall theorem
      * searching for an augmenting path
      * Berge theorem on the augmenting paths
      * algorithm based on Berge theorem

---

%GREEN% *Thursday, November 14, 2024 (Lessons 37-38):* %ENDCOLOR%

*The centralized deployment of Mobile sensors i.e. the perfect matching in Bipartite graphs (2)*
   * maximum matching in a bipartite graph (2)
      * Hopcroft & Karp algorithm
      * augmenting paths
      * an algorithm based on searching augmenting paths
      * ILP formulation
   * Maximum matching in general graphs
      * blossoms
      * lemma on the cycle contraction
      * Edmonds algorithm (idea)
   * Another application


%GREEN% *Monday, November 18, 2024 (Lessons 39-40-41):* %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
      * hypothesis of general position
      * properties
      * complexity
      * the dual problem: Delaunay triangulation
   * Algorithms to compute the Voronoi diagram
      * half-plane intersection (divide et impera)
      * Fortune algorithm


%GREEN% *Thursday, November 21, 2024 (Lessons 42-43):* %ENDCOLOR%

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

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


%GREEN% *Monday, November 25, 2024 (Lessons 44-45-46):* %ENDCOLOR%

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

*Other kinds of networks: the phylogeny and medicine cases (+some open problems) (1)*
   * Networks from biology (1)
      * Co-evolution
      * Definition of Reconciliation

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


%GREEN% *Thursday, November 28, 2024 (Lessons 47-48):* %ENDCOLOR%

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



%RED% *Monday, December 2, 2024:* %ENDCOLOR%

No lesson: Free time to finalize students' lessons

*STUDENTS' LESSON SCHEDULE - CONFIRMED*

%GREEN% *Thursday, December 5, 2024 (Lessons 49-50):* %ENDCOLOR%

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


%GREEN% *Monday, December 9, 2024 (Lessons 51-52-53):* %ENDCOLOR%

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


%RED% *Thursday, December 12, 2024:* %ENDCOLOR%

IT meeting - No lesson


%GREEN% *Monday, December 16, 2024 (Lessons 54-55-56):* %ENDCOLOR%

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


%RED% *Thursday, December 19, 2024 (Lessons 62-63):* %ENDCOLOR%

*SECOND MID-TERM EXAM*


%RED% *Monday, December 23, 2024:* %ENDCOLOR%
*NO LESSON*



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

<!--

Commento
-->
This topic: Algoreti > WebHome1011 > DiarioDelleLezioni
Topic revision: r195 - 2024-11-27 - TizianaCalamoneri