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]

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

Wednesday December 8, 2021: HOLIDAY

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

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

Students' lessons [M95], [Cal15]

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

Students' lessons [HZ14], [YWD06], [NSM16], [ML18] (these lessons could be anticipated to Dec. 10 if the program is finished)

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

Wednesday December 22, 2021: no lesson (unless it becomes necessary)

Lesson Diary of the Previous Years


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