direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Page Content

Network Algorithms (Lecture, WS 2017/18)

The goal of this lecture is to provide the students with tools and techniques to reason about efficient network algorithms. The lecture is problem-oriented and structured into different fundamental principles, such as Randomization, Decentralization, Indirection, etc. Each lecture will cover a different basic problem (such as Load Balancing, Medium Access, Symmetry Breaking, etc.) and will be self-contained.

 

 

News

  • First lecture: Wednesday October 18th, 2017, 2:00 - 4:00 p.m., room MAR 4.064
  • Please hand in the solutions for exercise sheet 1 either on ISIS before 2:00 p.m. Wednesday or right before the lecture in person to Georgios.

    For any open questions regarding ISIS, the worksheets or the tutorials, you can contact Damien Foucard.

Overview

Information
Lecturers:
Georgios Smaragdakis

Contact persons:
Damien Foucard (contact, tutorial management)
Event type:
Lecture with tutorial (VL+UE)
Area:

Compulsory elective module in the programs Master Computer Science (focus: Communication Systems (KS), Master Computer Engineering (focus: Technical Applications) Master Computer Engineering (StO/PO 2012): Studienschwerpunkt Netze (Networks; Elektrotechnik, Technische Informatik oder Informatik).
Modules:
Lecture plus tutorial are the Module MINF-KT-NA.W12.
SWS:
4
LP (ECTS):
6
Time:
Wednesday, 2pm–4pm weekly
First Meeting:
Lecture: 18.10.2017
Room:
MAR 4.064
Tutorial:
Thursday, 2pm–4pm weekly
Course ID:
0432 L 815
Audience:
master students, and Diplom students
Prerequisites:
 

  • BINF-GL - MPGI1 Algorithmische und funktionale Lösung diskreter Probleme

  • BINF-GL - MPGI2 Algorithmen und Datenstrukturen im imperativen Stil

    english language

 
Exam:
There is a written exam. In order to register for the exam the sutdens must obtain at least 50% of the points for exercises and/or programming assignments.
Further Information:
s. ISIS

Topics

Exemplary list of topics addressed in this lecture:

  • Models for networks and distributed systems
  • Robust and efficient network design: self-stabilization and self-optimization
  • Decentralization: Why and how? And complexity measures
  • Randomization: Why and how? Basic tools
  • Algorithms: Local algorithms, random algorithms, online algorithms, dynamic programming
  • Network Algorithms for leader election, coloring, maximal independent sets, Medium Access
  • Resource Allocation and embedding (e.g., energy, bandwidth, CPU)
  • Flow & congestion control, routing
  • Social networks: An algorithmic perspective

Organization

ISIS

If you are interested in attending, please make sure you are subscribed to the corresponding ISIS Web site to receive information and announcements.

Language

The lecture and the tutorials will be held in English.

Tutorials

You need 50% of the possible points to pass the tutorials.

Exam

The details for registering for the exam are to be announced and will be given in the lecture and the tutorials as well.

General References

  • David Peleg: Distributed Computing – A Locality-Sensitive Approach, SIAM 2000.

  • Michael Mitzenmacher and Eli Upfal, Probability and Computing, Cambridge University Press, 2005
  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, MIT press, 2009
  • Hagit Attiya and Jennifer Welch, Distributed Computing Fundamentals, Simulations, and Advanced Topics, John Wiley and Sons, Inc. 2005
  • Maurice Herlihy and Nir Shavit, The Art of Multiprocessor Programming, Morgan Kaufmann, 2012

Zusatzinformationen / Extras

Quick Access:

Schnellnavigation zur Seite über Nummerneingabe

Auxiliary Functions

Network Algorithms
Integrierte LV (VL mit UE)

Lecturer: Georgios Smaragdakis

Period:
14.10.2013 to 15.02.2014

We 14:00 - 16:00 o'clock
Th 14:00 - 16:00 o'clock

Location: MAR 4.064