Algorithms for Telecommunication
Ubinet track - Master IFI - University of Nice-Sophia Antipolis

The goal of this class is to show how combinatorial tools can be used to improve telecom networks.

Class document: pdf (5 chapters)
Going further: An extended version of the notes pdf (14 chapters)

#### Combinatorial Algorithms:

Session 1: Introduction to graphs.
- Graph, basic concepts (Chapter 1).
- Search in graphs and digraphs (Chapter 2).

Session2: Algorithms in edge-weighted graphs (Chapter 3).
- Dijkstra's algorithm or computing shortest paths.
- What about spanning trees or Boruvka-Kruskal algorithms.

Session 3: Solving flow problems (Chapter 4).
- Ford-Fulkerson algorithm.

Session 4: Applications of flow problems and other things.

Going further:
- Connectivity (Chapter 5 of the extended notes).
- Matching (Chapter 6 of the extended notes).
- Coloring (Chapter 8 of the extended notes).

#### Linear Programming: (Chapter 5)

Session 1: Introduction to linear programming slides.
Modelling combinatorial problems slides.

Session 2: Duality or assessing the quality of a solution slides.

Session 3: Solving problems in practice or using solvers (Glpk and Sagemath) pdf.
- Sagemath worksheet: Minimum vertex cover worksheet.

Session 4: Approximation algorithms via fractional relaxation slides.

Going further:
- Simplex Algorithm or Solving linear programmes slides.
- Polynomial Methods or Solving linear programmes when you are not in a hurry (The ellipsoid method) (Chapter 10 of the extended notes).
- Approximation techniques (Lagrangian relaxation, Fractional relaxation, Primal-Dual algorithms) (Chapters 11, 12, 13 of the extended notes).

#### Exam archives:

2017-2018: final exam, first exam.
2016-2017: final exam, first exam.
2015-2016: final exam
2014-2015: final exam, first exam.