Universität Wien

052114 VU Distributed and Parallel Algorithms (2025S)

6.00 ECTS (4.00 SWS), SPL 5 - Informatik und Wirtschaftsinformatik
Prüfungsimmanente Lehrveranstaltung
Moodle
Mo 28.04. 16:45-18:15 Hörsaal 3, Währinger Straße 29 3.OG

An/Abmeldung

Hinweis: Ihr Anmeldezeitpunkt innerhalb der Frist hat keine Auswirkungen auf die Platzvergabe (kein "first come, first served").

Details

max. 25 Teilnehmer*innen
Sprache: Englisch

Lehrende

Termine (iCal) - nächster Termin ist mit N markiert

  • Montag 03.03. 16:45 - 18:15 Hörsaal 3, Währinger Straße 29 3.OG
  • Dienstag 04.03. 13:15 - 14:45 Seminarraum 6, Währinger Straße 29 1.OG
  • Montag 10.03. 16:45 - 18:15 Hörsaal 3, Währinger Straße 29 3.OG
  • Dienstag 11.03. 13:15 - 14:45 Seminarraum 6, Währinger Straße 29 1.OG
  • Montag 17.03. 16:45 - 18:15 Digital
  • Dienstag 18.03. 13:15 - 14:45 Digital
  • Montag 24.03. 16:45 - 18:15 Hörsaal 3, Währinger Straße 29 3.OG
  • Dienstag 25.03. 13:15 - 14:45 Seminarraum 6, Währinger Straße 29 1.OG
  • Montag 31.03. 16:45 - 18:15 Hörsaal 3, Währinger Straße 29 3.OG
  • Dienstag 01.04. 13:15 - 14:45 Seminarraum 6, Währinger Straße 29 1.OG
  • Montag 07.04. 16:45 - 18:15 Hörsaal 3, Währinger Straße 29 3.OG
  • Dienstag 08.04. 13:15 - 14:45 Seminarraum 6, Währinger Straße 29 1.OG
  • Dienstag 29.04. 13:15 - 14:45 Seminarraum 6, Währinger Straße 29 1.OG
  • Montag 05.05. 16:45 - 18:15 Hörsaal 3, Währinger Straße 29 3.OG
  • Dienstag 06.05. 13:15 - 14:45 Seminarraum 6, Währinger Straße 29 1.OG
  • Montag 12.05. 16:45 - 18:15 Hörsaal 3, Währinger Straße 29 3.OG
  • Dienstag 13.05. 13:15 - 14:45 Seminarraum 6, Währinger Straße 29 1.OG
  • Montag 19.05. 16:45 - 18:15 Hörsaal 3, Währinger Straße 29 3.OG
  • Dienstag 20.05. 13:15 - 14:45 Seminarraum 6, Währinger Straße 29 1.OG
  • Montag 26.05. 16:45 - 18:15 Hörsaal 3, Währinger Straße 29 3.OG
  • Dienstag 27.05. 13:15 - 14:45 Seminarraum 6, Währinger Straße 29 1.OG
  • Montag 02.06. 16:45 - 18:15 Hörsaal 3, Währinger Straße 29 3.OG
  • Dienstag 03.06. 13:15 - 14:45 Seminarraum 6, Währinger Straße 29 1.OG
  • Dienstag 10.06. 13:15 - 14:45 Seminarraum 6, Währinger Straße 29 1.OG
  • Montag 16.06. 16:45 - 18:15 Hörsaal 3, Währinger Straße 29 3.OG
  • Dienstag 17.06. 13:15 - 14:45 Seminarraum 6, Währinger Straße 29 1.OG
  • Montag 23.06. 16:45 - 18:15 Hörsaal 3, Währinger Straße 29 3.OG
  • Dienstag 24.06. 13:15 - 14:45 Seminarraum 6, Währinger Straße 29 1.OG
  • Montag 30.06. 16:45 - 18:15 Hörsaal 3, Währinger Straße 29 3.OG

Information

Ziele, Inhalte und Methode der Lehrveranstaltung

This course will be taught in English and will take place on-site. Learning materials, such as slides and reading material, will be available on Moodle.

The course aims to provide an understanding of parallelism as a computing primitive and the challenges that arise in distributed and parallel algorithms. We will study the theoretical foundations of basic problems and also cover state-of-the-art developments in these two sub-areas of algorithm design.

Topics:

* Distributed (Graph) Algorithms:
- Different models of computations: LOCAL, CONGEST, CONGESTED Clique
- Problems: coloring, breadth-first-search (BFS), all-pairs shortest paths (APSP), diameter, cycle detection, spanners, spectral sparsification
- Design and analysis of algorithms, hardness results (a.k.a lower bounds)

* Parallel Algorithms:
- Parallel architectures and algorithm design principles
- Model of computation: PRAM
- Problems: Matrix multiplication, minimum spanning tree, shortest paths, connectivity

At the end of the course, you should be able to recognize which paradigm would be best suited for solving new problems, as well as study the correctness and the time complexity of your suggested solutions.

The lectures are complemented by several exercises and quizzes. Additionally, there will be an oral exam at the end of the semester.

It is highly recommended that you have completed the following courses:

- Discrete Mathematics – equivalent to 051110 VO Mathematical Foundations of Computer Science 1
- Introduction to Algorithms and Data Structures – equivalent to 051024 VU Algorithms and Data Structures 1

Art der Leistungskontrolle und erlaubte Hilfsmittel

The overall grade will consist of the following three components:

40% Exercises (individual work)
10% Quizzes (individual work)
50% Final Oral Exam (50%)

In addition, up to a 15% bonus can be obtained as follows:
- 5% bonus if you miss at most 3 classes (-1 for every additional missed class)
- 10% bonus if you solve bonus exercises

Presence is mandatory for the first lecture. Otherwise, it is not a requirement, but strongly recommended.
There is no minimum required number of points per exam/exercise sheet/quiz.

Mindestanforderungen und Beurteilungsmaßstab

>= 89%, grade 1
>= 76%, grade 2
>= 63%, grade 3
>= 50%, grade 4
< 50%, grade 5

Prüfungsstoff

All topics covered in class, the reading material, the exercises, and the quizzes.

Literatur

- Lecture notes by Roger Wattenhofer (https://disco.ethz.ch/courses/podc_allstars/ ), and by Jukka Suomela (https://users.ics.aalto.fi/suomela/da/ ).

- Joseph F. JáJá: An Introduction to Parallel Algorithms. Addison-Wesley, 1992

- Ananth Grama, Anshul Gupta, George Karypis, Vipin Kumar: Introduction to Parallel Computing. Addison Wesley, 2003

- Peter Sanders, Kurt Mehlhorn, Martin Dietzfelbinger, Roman Dementiev: Sequential and Parallel Algorithms and Data Structures - The Basic Toolbox. Springer, 2019.

Zuordnung im Vorlesungsverzeichnis

Module: DPA

Letzte Änderung: Mi 12.03.2025 13:05