Lesson Diary of the Previous Years

Lesson Diary A.y. 2022-2023

Tuesday September 27, 2022 (Lessons 1-2-3):

Introduction

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

  • The routing Problem
  • The shortest path Problem
    • shortest paths: BFS
  • The least cost path Problem (1)
    • the negative cycle issue
    • least cost paths: introduction
    • Bellman-Ford algorithm
    • Dijkstra algorithm

Friday September 30, 2022 (Lessons 4-5):

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

Tuesday October 4, 2022 (Lessons 6-7-8):

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

Friday October 7, 2022 (Lessons 9-10):

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

Tuesday October 11, 2022 (Lessons 11-12-13):

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

Friday October 14, 2022 (Lessons 14-15):

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

Tuesday October 18, 2022 (Lessons 16-17-18):

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

  • Direct and hidden collisions, interference graph
  • Introduction to the frequency assignment problems
  • Direct and hidden collisions, interference graph
  • L(h,k)-labeling and minimum span (1)
    • The special case h=k in relation to the suqre of a graph
    • Properties of the L(h,k)-labeling and their proofs
    • Proof of NP-completeness for diameter 2 graphs

Friday October 21, 2022 (Lessons 19-20):

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

Tuesday October 25, 2022 (Lessons 21-22-23):

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

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

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

Friday October 28, 2022 (Lessons 24-25):

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

Tuesday November 1, 2022: HOLIDAY

Friday November 4, 2022 (Lessons 26-27):

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

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

Tuesday November 8, 2022 (Lessons 28-29-30):

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

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

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

Tuesday November 15, 2022 (Lessons 34-35-36):

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

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

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

Friday November 18, 2022 (Lessons 37-38):

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

Tuesday November 22, 2022 (Lessons 39-40-41):

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

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

Friday November 25, 2022 (Lessons 42-43):

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

Tuesday November 29, 2022 (Lessons 44-45-46):

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

students'opinions questionnaire - OPIS code: R053WYBC

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

Friday December 2, 2022 (Lessons 47-48):

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

Tuesday December 6, 2022 (Lessons 49-50-51):

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

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

Friday December 9, 2022: LONG WEEKEND: the University is closed

Tuesday December 13, 2022 (Lessons 52-53-54)

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

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

Friday December 16, 2022 (Lessons 55-56): no lesson

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

Lesson Diary A.y. 2021-2022

Wednesday September 22, 2021 (Lessons 1-2-3):

Introduction

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

  • The routing Problem
  • The shortest path Problem
    • shortest paths: BFS
  • The least cost path Problem
    • the negative cycle issue
    • least cost paths: introduction

Friday September 24, 2021:

No lesson

Wednesday September 29, 2021 (Lessons 4-5-6):

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

Friday October 1, 2021 (Lessons 7-8):

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

Wednesday October 6, 2021 (Lessons 9-10-11):

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

Friday October 8, 2021 (Lessons 12-13):

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

Wednesday October 13, 2021 (Lessons 14-15-16):

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

Friday October 15, 2021 (Lessons 17-18):

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

Wednesday October 20, 2021 (Lessons 19-20-21):

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

Friday October 22, 2021 (Lessons 22-23):

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)

Wednesday October 27, 2021 (Lessons 24-25-26):

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

Friday October 29, 2021 (Lessons 27-28-29):

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

Week November 2-5, 2021: Mid-term exams

Wednesday November 10, 2021 (Lessons 30-31-32): 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)

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

  • The MST problem
    • Kruskal algorithm
    • Prim algorithm
    • Boruvka algorithm

Wednesday November 17, 2021 (Lessons 35-36-37):

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

Friday November 19, 2021 (Lessons 38-39):

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

Wednesday November 24, 2021 (Lessons 40-41-42):

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

Friday November 26, 2021 (Lessons 43-44):

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

Wednesday December 1, 2021 (Lessons 45-46-47):

Students' lessons

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

Friday December 3, 2021 (Lessons 48-49):

Students' lessons [BKTL04], [BPT00], [Bal07], [AGK08], [Xal14]

Wednesday December 8, 2021: HOLIDAY

Friday December 10, 2021 (Lessons 50-51):

Students' lessons [M95], [Cal15]

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

Wednesday December 15, 2021 (Lessons 52-53-54):

Students' lessons [HZ14], [YWD06], [NSM16], [ML18]

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)

Friday December 17, 2021 (Lessons 55-56): mid-term exam

Wednesday December 22, 2021: no lesson

--

Lesson Diary A.y. 2020-2021

Wednesday October 7, 2020 (Lessons 1-2-3):

Introduction

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

  • The routing Problem
  • The shortest path Problem
    • shortest paths: BFS
  • The least cost path Problem
    • the negative cycle issue
    • least cost paths: introduction

Friday October 9, 2020 (Lessons 4-5):

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

Wednesday October 14, 2020 (Lessons 6-7-8):

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

Friday October 16, 2020 (Lessons 9-10):

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

  • Layout of the Butterfly network
    • the Even & Even layout
    • comparison between the two methods
  • Layout of the Hypercube network
    • Collinear layout
    • general layout
  • The 3D layout problem

Wednesday October 21, 2020 (lessons 11-12-13):

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

Friday October 23, 2020 (lessons 14-15):

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

Wednesday October 28, 2020 (lessons 16-17-18): A Frequency assignment problem i.e. the L(h,k)-Labeling Problem (2)

  • L(h,k)-labeling and minimum span (2)
    • Proof of NP-completeness for diameter 2 graphs
    • Lower bound of Delta+1 on 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

Friday October 30, 2020 (lessons 19-20):

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)

Wednesday November 4, 2020 (lessons 21-22-23):

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

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

Friday November 6, 2020 (lessons 24-25):

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

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

Wednesday November 11, 2020 (lessons 26-27-28):

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

Friday November 13, 2020 (lessons 29-30):

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

Wednesday November 18, 2020 (lessons 31-32-33):

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

Friday November 20, 2020 (lessons 34-35):

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)

Wednesday November 25, 2020 (lessons 36-37-38):

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

Friday November 27, 2020 (lessons 39-40):

Mid Term Exam 1/2

Wednesday December 2, 2020 (lessons 41-42-43):

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

Friday December 4, 2020 (lessons 44-45):

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

Wednesday December 9, 2020 (lessons 46-47-48):

Students' lessons (4)

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

Friday December 11, 2020 (lessons 49-50):

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

Wednesday December 16, 2020 (lessons 51-52-53):

Students' lessons (5)

Friday December 18, 2020 (lessons 54-55):

Mid Term Exam 2/2


Lesson Diary A.y. 2019-2020

Wednesday September 25, 2019 (Lessons 1-2-3):

Introduction

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

  • The routing Problem
  • The shortest path Problem
    • shortest paths: BFS
  • The least cost path Problem
    • the negative cycle issue
    • least cost paths: introduction
    • Bellman-Ford algorithm
    • Dijkstra algorithm
    • Floyd-Warshall algorithm

Friday September 27, 2019 (Lessons 4-5):

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

Wednesday October 2, 2019 (Lessons 6-7-8):

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

Friday October 4, 2019 (lessons 9-10):

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

Wednesday October 9, 2019 (lessons 11-13):

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

Friday October 11, 2019 (lessons 14-15):

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

Wednesday October 16, 2019 (lessons 16-18):

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

Friday October 18, 2019 (lessons 19-20):

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

Wednesday October 23, 2019 (lessons 21-23):

Lesson cancelled (due to illness of the teacher)

Friday October 25, 2019 (lessons 24-25):

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)

Wednesday October 29, 2019 (lessons 26-28):

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

Friday November 1, 2019 (lessons 26-27):

Holiday

Wednesday November 6, 2019 (lessons 28-30):

Midterm Exam

Friday November 8, 2019 (lessons 31-32):

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

Wednesday November 13, 2019 (lessons 33-35):

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

Friday November 15, 2019 (lessons 36-37):

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

Wednesday November 20, 2019 (lessons 38-40):

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

Friday November 22, 2019 (lessons 41-42): 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)

Wednesday November 27, 2019 (lessons 43-45):

Student Lessons with the presence of the teacher (3)

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

EVALUATION OF THE COURSE

Friday November 29, 2019 (lessons 46-47):

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

Wednesday December 4, 2019 (lessons 48-50):

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)

Friday December 6, 2019 (lessons 51-52):

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

Wednesday December 11, 2019 (lessons 51-53):

Student Lessons with the presence of the teacher (5)

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

Winner Announcement: Award for the best students' lesson

Friday December 13, 2019 (lessons 53-54):

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

Wednesday December 18, 2019 (lessons 55-57):

Midterm Exam

Lesson Diary A.y. 2018-2019

Tuesday September 25, 2018 (Lessons 1-2,5):

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

Thursday September 27, 2018 (Lessons 2,5-5):

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

Tuesday October 2, 2018 (Lessons 5-7,5):

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

Thursday October 4, 2018 (lessons 7,5-10):

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

  • Relation between bisection width and layout area
  • Layout of the Butterfly network (1)
    • the Wise layout
    • the Even & Even layout
    • comparison between the two methods

Tuesday October 9, 2018 (lessons 10-12,5):

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

Thursday October 11, 2018 (lessons 12,5-15):

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

Tuesday October 16, 2018 (lessons 15-17,5):

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

Thursday October 18, 2018 (lessons 17,5-20):

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

Tuesday October 23, 2018 (lessons 20-22,5):

Student Lessons with the presence of the teacher (1)

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

Thursday October 25, 2018 (lessons 22,5-25):

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

Tuesday October 30, 2018:

Lesson canceled by the Dean.

Thursday November 1, 2018:

Holiday.

Tuesday November 6, 2018 (lessons 25-27,5):

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)

Thursday November 8, 2018 (lessons 27,5-30):

Mid term exam

Tuesday November 13, 2018 (lessons 30-32,5):

Student Lessons with the presence of the teacher (2)

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

Thursday November 15, 2018 (lessons 32,5-35):

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

Tuesday November 20, 2018 (lessons 35-37,5):

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

Thursday November 22, 2018 (lessons 37,5-40):

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

Tuesday November 27, 2018:

NO LESSON

Thursday November 29, 2018 (lessons 40-42,5): 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

Tuesday December 4, 2018 (lessons 42,5-45):

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

Thursday December 6, 2018 (lessons 45-47,5):

Distributed Deployment 2

Tuesday December 11, 2018 (lessons 47,5-50):

Student Lessons with the presence of the teacher (3)

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

Thursday December 13, 2018 (lessons 50-52,5):

UAVs 1

Tuesday December 18, 2018 (lessons 52,5-55):

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

Tuesday December 20, 2018 (lessons 55-57,5):

Student Lessons with the presence of the teacher (4)

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

Lesson Diary A.y. 2017-2018

Friday September 29, 2017 (Lessons 1-2,5):

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

Monday October 2, 2017 (Lessons 2,5-5):

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

Friday October 6, 2017 (Lessons 5-7,5):

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

Monday October 9, 2017 (lessons 7,5-10):

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

Friday October 13, 2017 (lessons 10-12,5):

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

Monday October 16, 2017 (lessons 12,5-15):

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

Friday October 20, 2017 (lessons 15-17,5):

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

Monday October 23, 2017 (lessons 17.5-20):

Student Lessons with the presence of the teacher (1)

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

Friday October 27, 2017 (lessons 20-22.5):

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

Monday October 30, 2017 (lessons 22.5-25):

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)

Friday November 3, 2017 (lessons 25-27.5): 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

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

Friday November 10, 2017 (lessons 30-32.5):

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

Monday November 13, 2017 (lessons 32.5-35):

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

Friday November 17, 2017 (lessons 35-37.5):

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

Monday November 20, 2017 (lessons 37.5-40):

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

Friday November 24, 2017 (lessons 40-42.5):

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

Monday November 27, 2017 (lessons 42.5-45):

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

Friday December 1, 2017 (lessons 45-47.5):

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

Monday December 4, 2017 (lessons 47.5-50):

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

Friday December 8, 2017:

Holiday

Monday December 11, 2017 (lessons 50-52.5):

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

Some theses proposals

Some problems in (co-)Phylogeny

Some other theses proposals

Friday December 15, 2017 (lessons 52.5-55):

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

Monday December 18, 2017 (lessons 55-57.5):

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

Friday December 22, 2017 (lessons 57.5-60):

Mid term exam

Previous years' Diaries

Lesson Diary A.y. 2016-2017

Monday September 26, 2016 (Lessons 1-2):

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

Friday September 30, 2016 (Lessons 3-4):

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

Monday October 3, 2016 (Lessons 5-6):

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

Friday October 7, 2016 (lessons 7-8):

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

Monday October 10, 2016 (lessons 9-10):

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

Friday October 14, 2016 (lessons 11-12):

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

Monday October 17, 2016 (lessons 13-14):

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

Friday October 21, 2016 (lessons 15-16):

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

Monday October 24, 2016 (lessons 17-18): 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

Friday October 28, 2016 (lessons 19-20): 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)

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

Friday November 4, 2016 (lessons 23-24): 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

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

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

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

Friday November 18, 2016 (lessons 31-32): 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

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

Friday November 25, 2016 (lessons 35-36):

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

  • (mobile) sensor networks
  • the problem of centralized deployment
  • the problem on graphs: min weight matching in 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

Monday November 28, 2016 (lessons 37-38):

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)

Friday December 2, 2016 (lessons 39-40):

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)

Monday December 5, 2016 (lessons 41-42):

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

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

Monday December 12, 2016 (lessons 45-46): Student lessons

Friday December 16, 2016 (lessons 47-48): IT meeting

Monday December 19, 2016 (lessons 49-50): Student lessons

Tuesday December 20, 2016 (lessons 51-52): Student lessons

Lesson Diary A.y. 2015-2016

Tuesday September 22, 2015 (Lessons 1-2):

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

Friday September 25, 2015 (Lessons 3-4):

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

Tuesday September 29, 2015 (Lessons 5-6):

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

Friday October 2, 2015 (lessons 7-8):

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

Friday October 2, 2015 (lessons 9-10):

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

Tuesday October 6, 2015 (lessons 11-12):

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

Tuesday October 9, 2015 (lessons 13-14):

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

Tuesday October 13, 2015 (lessons 15-16):

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

Tuesday October 20, 2015 (lessons 17-18):

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

Friday October 23, 2015 (lessons 19-20):

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

Tuesday October 27, 2015 (lessons 21-22):

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

Friday October 30, 2015 (lessons 23-24):

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

Friday November 6, 2015:

Mid term exam

Tuesday November 10, 2015 (lessons 25-26):

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

Friday November 13, 2015 (lessons 27-28):

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

Tuesday November 17, 2015 (lessons 29-30):

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)

Friday November 20, 2015 (lessons 31-32):

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)

Tuesday November 24, 2015 (lessons 33-34):

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

Lesson Diary A.y. 2014-2015

Tuesday September 29, 2014 (Lessons 1-2):

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

Friday October 3, 2014 (Lessons 3-4):

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

Tuesday October 7, 2014 (Lessons 5-6):

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)

Friday October 10, 2014 (lessons 7-8):

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

Tuesday October 14, 2014 (lessons 9-10):

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

Tuesday October 17, 2014 (lessons 11-12):

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

Tuesday October 21, 2014 (lessons 13-14):

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

Friday October 24, 2014:

No lesson because of bus and train strike

Tuesday October 28, 2014 (lessons 15-16):

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

Friday October 31, 2014 (lessons 17-18):

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

Tuesday November 4, 2014 (lessons 19-20):

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

Friday November 7, 2014 (lessons 21-22):

Mid term exam

Tuesday November 11, 2014 (lessons 23-24):

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)

Friday November 14, 2014 (lessons 25-26):

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

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

Tuesday November 18, 2014 (lessons 27-28):

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

Friday November 21, 2014 (lessons 29-30):

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)

Tuesday November 25, 2014 (lessons 31-32):

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

Tuesday December 2, 2014 (lessons 35-36):

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

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

Friday December 5, 2014 (lessons 37-38):

Student lessons (1)

Tuesday December 9, 2014 (lessons 39-40):

Student lessons (2)

Tuesday December 16, 2014 (lessons 41-42):

Student lessons (3)

Lesson Diary A.y. 2013-2014

Monday September 30, 2013 (Lessons 1-2):

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

Friday October 4, 2013 (lessons 3-4):

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

Monday October 7, 2013 (lessons 5-6):

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

Friday October 11, 2013 (lessons 7-8):

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

Monday October 14, 2013 (lessons 9-10):

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

Friday October 18, 2013 (lessons 11-12):

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
  • 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

Monday October 21, 2013 (lessons 13-14):

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

Friday October 25, 2013 (lessons 15-16):

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

Monday October 28, 2013 (lessons 17-18):

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

Monday November 4, 2013 (lessons 19-20):

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

Friday November 8, 2013 (lessons 21-22):

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

week November 11-15: No classes - midterm exams

Monday November 18, 2013 (lessons 23-24):

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

Friday November 22, 2013 (lessons 25-26): 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)

Monday December 2, 2013 (lessons 27-28): 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

Friday December 6, 2013 (lessons 29-30): 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

Monday December 9, 2013 (lessons 31-32):

Student Lessons

Friday December 13, 2013 (lessons 33-34):

Student Lessons

Monday December 16, 2013 (lessons 35-36):

Student Lessons

Diario delle Lezioni A.A. 2012-2013

Mercoledi' 3 Ottobre 2011 (Ore 1-2):

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

Lunedi' 8 Ottobre 2012 (Ore 3-4):

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

Mercoledi' 10 Ottobre 2012 (Ore 5-6):

Il Problema dell'Instradamento ovvero 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

Lunedi' 15 Ottobre 2012 (Ore 7-8):

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

Mercoledi' 17 Ottobre 2012 (Ore 9-10):

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

Lunedi' 22 Ottobre 2012 (Ore 11-12):

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

Mercoledi' 24 Ottobre 2012 (Ore 13-14):

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

Lunedi' 29 Ottobre 2012 (Ore 15-16):

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

Lunedi' 5 Novembre 2012 (Ore 17-18):

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

Mercoledi' 7 Novembre 2012 (Ore 19-20): 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)

12-15 Novembre 2012: settimana di interruzione della didattica

Lunedi' 19 Novembre 2012 (Ore 21-22): 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

Mercoledi' 21 Novembre 2012 (Ore 23-24):

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

Lunedi' 26 Novembre 2012 (Ore 25-26):

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

Mercoledi' 28 Novembre 2012 (Ore 27-28):

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

Lunedi' 3 Dicembre 2012 (Ore 29-30):

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

Mercoledi' 5 Dicembre 2012 (Ore 31-32):

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

Diario delle Lezioni A.A. 2011-2012

Lunedi' 3 Ottobre 2011 (Ore 1-2):

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

Giovedi' 6 Ottobre 2011 (Ore 3-4):

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

Lunedi' 10 Ottobre 2011 (Ore 5-6):

Il Problema dell'Instradamento ovvero 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

Mercoledi' 12 Ottobre 2011 (Ore 7-8):

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

Lunedi' 17 Ottobre 2011 (Ore 9-10):

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

Mercoledi' 19 Ottobre 2011 (Ore 11-12):

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

Lunedi' 24 Ottobre 2011 (Ore 13-14):

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)

Mercoledi' 26 Ottobre 2011 (Ore 15-16):

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

Mercoledi' 9 Novembre 2011 (Ore 17-18):

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

Lunedi' 21 Novembre 2011 (Ore 19-20):

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)

Mercoledi' 23 Novembre 2011 (Ore 21-22): 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

Lunedi' 28 Novembre 2010 (Ore 23-24):

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

Mercoledi' 30 Novembre 2010 (Ore 25-26):

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

Lunedi' 5 Dicembre 2011 (Ore 27-28):

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'

Mercoledi' 7 Dicembre 2011 (Ore 29-30):

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

Lunedi' 12 Dicembre 2011 (Ore 31-32):

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

Mercoledi' 14 Dicembre 2011 (Lauree)

Vacanze natalizie

Mercoledi' 11 Gennaio 2012 (Ore 33-34):

Tesine

Lunedi' 16 Gennaio 2012 (Ore 35-36):

Tesine

Mercoledi' 18 Gennaio 2012 (Ore 37-38):

Tesine


Diario delle Lezioni A.A. 2010-2011

Lunedi' 18 Ottobre 2010 (Ore 1-2):

Lectio Magistralis: Dott. Prabhakar Raghavan

Giovedi' 21 Ottobre 2010 (Ore 3-4):

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

Lunedi' 25 Ottobre 2010 (Ore 5-6):

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

Giovedi' 28 Ottobre 2010 (Ore 7-8):

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

Lunedi' 1 Novembre 2010: festa

Giovedi' 4 Novembre 2010 (Ore 9-10):

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

Lunedi' 8 Novembre 2010 (Ore 11-12):

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

Giovedi' 11 Novembre 2010 (Ore 13-14):

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

Lunedi' 15 Novembre 2010 (Ore 15-16):

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

Giovedi' 18 Novembre 2010 (Ore 17-18):

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

Lunedi' 22 Novembre 2010 (Ore 19-20):

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

Giovedi' 25 Novembre 2010 (Ore 21-22):

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

Settimana di interruzione della didattica

Lunedi' 6 Dicembre 2010 (Ore 23-24):

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'

Giovedi' 9 Dicembre 2010 (Ore 25-26):

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)

Lunedi' 13 Dicembre 2010 (Ore 27-28):

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

Giovedi' 16 Dicembre 2010 (Lauree)

Lunedi' 20 Dicembre 2010 (Incontro con le aziende)

Vacanze natalizie

Lunedi' 10 Gennaio 2011 (Ore 29-30):

Tesine

Giovedi' 13 Gennaio 2011 (Ore 31-32):

Tesine

Venerdi' 14 Gennaio 2011 (Ore 33-34):

Tesine

Lunedi' 17 Gennaio 2011 (Ore 35-36):

Tesine

Giovedi' 20 Gennaio 2011 (Ore 37-38):

Tesine

-- Tiziana Calamoneri - 2021-09-23

Comments


This topic: Algoreti > WebHome1011 > DiarioDelleLezioni > PreviousYears
Topic revision: r3 - 2023-09-26 - TizianaCalamoneri
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2024 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback