English English

General Information

Type
Where and When
First Session
Lecturer/Tutor
VÜ4 Tu 10:00am - 11:30am / AH III
Thu 10:00am - 11:30am / AH III 		16 April 2009 Vöcking / Winkler
  • ECTS Credits: 6
  • Language: English
Extra reading for those Masterstudents needing 8 credits:
General: F. Thomson Leighton: Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes, Chapter 3.4.6 Bounding Queue Size, pages 571-591

Topic

The lecture introduces architectures and algorithms for computer networks. The focus lies on the theoretical analysis of these networks and the corresponding algorithms using methods from combinatorics (discrete structures) and probability theory. Besides classical topics like sorting and permutation routing on networks, the covers also more recent topics like the design of peer-to-peer networks and algorithms for communication in wireless networks. In particular, we study the following topics:

  • Permutation Routing on Meshes
  • Sorting networks
  • Oblivious Routing: Path Selection and Scheduling
  • Wireless Networks: Overlays and Scheduling
  • Peer-to-peer Networks (Chord)
  • Congestion Games

Examination

50 percent of the points from exercises needs to be achieved as prerequisites for admission of oral examination. Only master students can do an oral examination at the end of the semester. A "Leistungsnachweis (Übungsschein)" for this lecture will not be given to diplomastudents. The lecture and the exercises can be chosen to be part of the oral examination for diploma examination.

Master Examinations

The examinations are oral and focus on the content presented in the lectures. 46 percent of the points from exercises needs to be achieved as prerequisites for admission. Appointments are offered at the following days

July 23 / August 27 / September 17

Students can choose one of these dates and get assigned a 45 minutes slot between 10am and 6pm on the chosen day. The examination will take between 20 and 40 minutes. The result will be declared directly after the examination.

During the last exercise on Juli 21, students are asked to specify which date they prefer for the exam. At this point they must also specify whether they want to extend the exam from 6 to 8 credits; in which case the exam will be extended to the extra reading.

For those who fail the exam in the first attempt there will be a second chance on October 8.

Examination Dates

Examinations on July 23rd:

Time
Name
10:00
Christian Fuchs
10:45
Ijaz Ahmad
11:15
Irfan Mirza

Examinations on August 27th:

Time
Name
10:00
Neda Petreska
10:45
Neyla Rojas
11:15
Obaid Salikeen
14:00
Arham Muslim
14:45
Adnan Aziz
15:30
Wasif Masood

The examinations will take place in room 4024.

Diploma Examinations

The lecture can be chosen as part of the diploma examinations. The content of the lecture including the exercises accounts for 4 SWS. More details about diploma examinations at i1 can be found here .

Exam Preparation

List of questions.

Schedule

Date
Type
16.4.
lecture
21.4.
lecture
23.4.
lecture
28.4.
exercise
30.4.
lecture
5.5.
free (Fachschaftsvollversammlung)
7.5.
lecture
12.5.
lecture
14.5.
exercise
19.5.
lecture
21.5.
free (Christi Himmelfahrt)
26.5.
lecture
28.5.
lecture
2.6.
free (Pfingsten)
4.6.
free (Pfingsten)
9.6.
exercise
11.6.
free (Fronleichnam)
16.6.
lecture
18.6.
lecture
23.6.
exercise
25.6.
lecture
30.6.
lecture
2.7.
lecture
7.7.
exercise
9.7.
lecture
14.7.
lecture
16.7.
lecture
21.7.
exercise
23.7.
oral examination

Lecture notes

Literature

  • General: F. Thomson Leighton: Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes,
  • Chapter 1: Marc Baumslag and Fred Annexstein: A unified framework for off-line permutation routing in parallel networks, Theory of Computing Systems, 24, 233-251, 1991
  • Chapter 2: Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford. Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill, 2001, Chap. 27

Exercises

Masterstudents are asked to hand in the exercises in groups of at most two people.
The lecture notes and exercises can only be downloaded from inside the RWTH network. You can use the VPN Client to download them from places outside the University.

Contact

Melanie Winkler: winkler (at) cs (dot) rwth-aachen (dot) de