Lesson Diary A.y. 2023-2024

Monday, September 25, 2023 (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 (part)

Thursday, September 28, 2023 (Lessons 4-5):

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

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

Monday, October 2, 2023 (Lessons 6-7-8):

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

  • The Routing Problem on Interconnection Topologies
    • The Benes network
    • routing on the Benes network: the looping algorithm

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

  • The Thompson model
  • The orthogonal grid drawing of graphs
  • Layout of the complete binary tree (H-tree)
  • Collinear Layout of the Complete network
  • Layout of the Complete network
  • Relation between bisection width and layout area
  • Layout of the Butterfly network
    • The Wise layout

Thursday, October 5, 2023 (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
    • Optimal area layout

Monday, October 9, 2023 (Lessons 11-12-13):

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

  • Layout of the Hypercube network
    • Collinear layout
    • general layout
  • The 3D layout problem

The problem of worm propagation/prevention i.e. the Minimum Vertex Covering Problem (1)

  • The problem
    • worms
    • damages caused by worms
  • Model of the problem on graphs: minimum vertex cover
    • Definition
    • ILP model
    • a 2-approximation algorithm
    • independent set and maximum matching in relation to vertex cover
    • another approximation algorithm

Thursday October 12, 2023 (Lessons 14-15):

The problem of worm propagation/prevention i.e. the Minimum Vertex Covering Problem (2)

  • Model of the problem on graphs: minimum vertex cover * Konig-Egevary theorem (without proof)
  • A related problem: eternal vertex problem

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

  • Introduction to the frequency assignment problems

Monday October 16, 2023 (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 square of a graph
    • Properties of the L(h,k)-labeling and their proofs
    • Proof of NP-completeness for diameter 2 graphs
    • Lower bound of Delta+1 on lambda
    • Example: a graph requiring lambda=Delta squared - Delta
    • Upper bound of Delta squared + 2 Delta
    • Griggs and Yeh's conjecture
    • Exact results: cliques
    • Exact results: stars
    • Exact results: trees
    • Exact results: paths
    • Exact results: cycles
    • Exact results: grids
    • Approximate results: outerplanar graphs

Thursday, October 19, 2023 (Lessons 22-23):

Special guest: Jan Arne Telle - University of Bergen - https://www.uib.no/en/persons/Jan.Arne.Telle

Seminar entitled: Recognition of Linear and Star Variants of Leaf Powers is in P

Monday, October 23, 2023 (Lessons 24-25-26): A Frequency assignment problem i.e. the L(h,k)-Labeling Problem (3)

  • Variations of the problem
    • oriented L(2,1)-labeling
    • L(h1, ..., hk)-labeling
    • backbone coloring
    • multiple L(h,k)-labeling
  • a parenthesis on the 4-color theorem

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

  • The Min Broadcast problem
  • NP-completeness and inapproximability results (reduction from Min Set Cover)
  • Relation between Min Broadcast and Min Spanning Tree (MST)

Thursday, October 26, 2023 (Lessons 27-28):

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

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

Mid-term exam: first part

Monday, October 30, 2023 (Lessons 29-30-31):

The data mule problem i.e. the TSP

  • (Fixed) sensor networks
  • The Data Mule problem
  • The TSP
    • NP-completeness
    • inapproximability
    • special cases: metric TSP and Euclidean TSP
    • generalizations

The Data Collection in ad-hoc networks i.e. the connected Dominating Set Problem

  • the connected dominating set problem
  • the dominating set problem
  • the connected dominating set problems in unit disk graphs

Thursday, November 2, 2023 (Lessons 32-33):

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

  • (mobile) sensor networks

Mid-term exam: second part

Monday November 6, 2023 (Lessons 34-35-36):

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

  • The problem of centralized deployment
  • The problem on graphs: min weight matching in bipartite graphs
  • maximum matching in a bipartite graph
    • P. Hall theorem (with proof)
    • corollary to the P. Hall theorem
    • searching for an augmenting path
    • Berge theorem on the augmenting paths
    • algorithm based on Berge theorem
    • Hopcroft & Karp algorithm
    • augmenting paths
    • an algorithm based on searching augmenting paths
    • ILP formulation

Thursday, November 9, 2023 (Lessons 37-38):

Mid-term exam: third part

Monday November 13, 2023 (Lessons 39-40-41):

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

  • Maximum matching in general graphs
    • blossoms
    • lemma on the cycle contraction
    • Edmonds algorithm (idea)
  • Another application

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

  • The problem
  • A Possible Approach: Virtual Forces
  • A Protocol Based on Voronoi Diagrams
  • Voronoi Diagrams
    • hypothesis of general position
    • properties
    • complexity
    • the dual problem: Delaunay triangulation
    • half-plane intersection (divide et impera)

Thursday November 16, 2023 (Lessons 42-43):

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

  • Algorithms to compute the Voronoi diagram
    • Fortune algorithm

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

HERE: instructions for student's opinions questionnaire 2022/2023

Monday, November 20, 2023 (Lessons 44-45-46): The Distributed Deployment of Sensors i.e. the Construction of a Voronoi Diagram (3)

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

Monitoring by UAVs i.e. what? (+some open problems)

Thursday, November 23, 2023 Canceled

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

Thursday, November 30, 2023 Canceled

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

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

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

Thursday, December 14, 2023 Canceled

Monday, December 18, 2023 (Lessons 58-59-60):

Mid-term exam

Lesson Diary of the Previous Years


This topic: Algoreti > WebHome1011 > DiarioDelleLezioni
Topic revision: r178 - 2023-11-27 - 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