Tags:
create new tag
view all tags

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

Topic revision: r132 - 2021-10-21 - TizianaCalamoneri  Questo sito usa cookies, usandolo ne accettate la presenza. (CookiePolicy) Torna al Dipartimento di Informatica Deutsch English Español _Français_ Italiano  Copyright © 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