Computer Science Department
-
Technische Universität München
Chair for
Efficient Algorithms
Network Algorithms (WS 05/06)
Lecturer:
Prof. Dr. Christian Scheideler
Announcements:
Area:
4 lectures per week in area III (Theoretical Computer Science)
advanced course, topic algorithms
Time and Place:
Mon 08:30 - 10:00, lecture hall MW 1801
Fri 08:30 - 10:00, lecture hall MI HS 1
The first lecture takes place on Monday, October 17.
Course Certificate:
To get a course certificate students muss pass the exams.
Exams:
See the
German webpage
for details.
Audience:
graduate students of computer science
students with computer science as minor
Prerequisites:
1st and 2nd year courses
Recommended for:
In-depth knowledge in topic Algorithms
Contents:
The course will focus on the following topics:
Models for distributed algorithms and data structures
Network theory
Routing and scheduling
Hashing and caching
The continuous-discrete approach
Supervised overlay networks
Decentralized overlay networks
Anycasting and multicasting
Searching and sorting
Self-stabilizing overlay networks
Self-preserving overlay networks
Overlay networks for wireless systems
Logical networks for configware
Related and Advanced Lectures:
An advanced lecture is planned.
Lecture Notes:
Section 1: Introduction (in
postscript
and
pdf
)
Section 2: Network Theory (in
postscript
and
pdf
)
Section 3: Routing (in
postscript
and
pdf
)
Section 4: Scheduling (in
postscript
and
pdf
)
Section 5: Distributed data management I - Hashing (in
postscript
and
pdf
)
Section 6: Distributed data management II - Caching (in
postscript
and
pdf
)
Section 7: Supervised Overlay Networks I (in
postscript
and
pdf
)
Section 8: Supervised Overlay Networks II (in
postscript
and
pdf
)
Section 9: Decentralized Overlay Networks (in
postscript
and
pdf
)
Section 10: Locality-aware Overlay Networks (in
postscript
and
pdf
)
Section 11: Group Management (in
postscript
and
pdf
)
Section 12: Overlay Networks for Heterogeneous Peers (in
postscript
and
pdf
)
Section 13: Wireless Overlay Networks I (in
postscript
and
pdf
)
Section 14: Wireless Overlay Networks II (in
postscript
and
pdf
)
Programs:
Programs will be written in C++ using the Subjects environment that can be downloaded below.
Subjects environment
(Version 1.1)
A
Hello World
example.
A
Ping Pong
example.
Assignments (in German):
Assignment 1 (in
postscript
and
pdf
, due Oct. 28)
Assignment 2 (in
postscript
and
pdf
, due Nov. 4)
Assignment 3 (in
postscript
and
pdf
, due Nov. 18)
Assignment 4 (in
postscript
and
pdf
, due Nov. 25)
Assignment 5 (in
postscript
and
pdf
, due Dec. 2)
Assignment 6 (in
postscript
and
pdf
, due Dec. 23)
Assignment 7 (in
postscript
and
pdf
, due Jan. 20)
Assignment 8 (in
postscript
and
pdf
, due Jan. 27)
Assignment 9 (in
postscript
and
pdf
, due Feb. 03)
Assignment 10 (in
postscript
and
pdf
, due Feb. 10)
Solutions:
Solutions to problems in assignments 1 to 5:
Previous midterms to prepare for this year's midterm:
2002 (in
ps
and
pdf
) 2003 (in
ps
and
pdf
) 2004 (in
ps
and
pdf
)
References:
The course is based on recent conference publications. References will be given in the lecture notes.
Office Hours:
look here
Last Changes:
Hanjo Täubig
on 04/10/2005