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
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: |
|
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
ISIS
If you are interested in attending, please make sure you are subscribed to the corresponding ISIS website to receive information and announcements.
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 slides
- 01. netalg13-intro PDF, 3 MB
- 02. netalg13 topology PDF, 2 MB
- 03. netalg13 leader election PDF, 505 KB
- 04. netalg13 consensus PDF, 656 KB
- 05. netalg13 tree algorithms PDF, 981 KB
- 06. netalg13 coloring PDF, 571 KB
- 07. netalg13 MIS PDF, 620 KB
- 08. netalg13 Sorting PDF, 600 KB
- 09. netalg13 Counting PDF, 595 KB
- 10. netalg13 Self stabilization PDF, 844 KB
- 11. netalg13 Synchronization PDF, 434 KB
Lecture nodes
- Lecture Notes - Network Algorithms PDF, 635 KB
Exercise Sheets
- 01. NA-Ex1 PDF, 177 KB
- 02. NA-Ex2 PDF, 207 KB
- 03. NA-Ex3 PDF, 136 KB
- 04. NA-Ex4 PDF, 169 KB
- 05. NA-Ex5 PDF, 149 KB
- 06. NA-EX6 PDF, 133 KB
- 07. NA-EX7 PDF, 177 KB
- 08. NA-Ex8 PDF, 148 KB
- 09. NA-Ex9 PDF, 144 KB
- 10. NA-Ex10 PDF, 162 KB
- 11. NA-Ex11 PDF, 205 KB
- 12. NA-Ex12 PDF, 123 KB
- 13. NA-Ex13 PDF, 97 KB
- 14. NA-Ex14 PDF, 102 KB
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:
Auxiliary Functions
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