direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Page Content

Network Algorithms (Lecture, WS 2013/14)

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 16th, 2013, 1:00 - 3:00 p.m., room MAR 0.007
  • Please hand in the solutions for exercise sheet 1 either on ISIS before 13:00 Wednesday or right before the lecture in person to Stefan.

    For any open questions regarding ISIS, the worksheets or the tutorials
    you can contact Arne Ludwig.

Overview

Information
Lecturers:
Stefan Schmid

Contact persons:
Arne Ludwig (contact, tutorial management)
Srivatsan Ravi
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, 1pm–3pm weekly
First Meeting:
Lecture: 16.10.2013
Room:
MAR 0.007
Tutorial:
Wednesday, 3pm–5pm 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 website 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.

Lecture nodes

Exercise Sheets

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

Font size:
smaller
default
bigger

Network Algorithms
Integrierte LV (VL mit UE)

Lecturer: Stefan Schmid

Period:
14.10.2013 to 15.02.2014

We 13:00 - 17:00 o'clock

Location: MAR 0.007

ISIS