052114 VU Distributed and Parallel Algorithms (2025S)
Continuous assessment of course work
Labels
Registration/Deregistration
Note: The time of your registration within the registration period has no effect on the allocation of places (no first come, first served).
- Registration is open from Mo 10.02.2025 09:00 to Fr 21.02.2025 09:00
- Deregistration possible until Fr 14.03.2025 23:59
Details
max. 25 participants
Language: English
Lecturers
Classes (iCal) - next class is marked with N
- Monday 03.03. 16:45 - 18:15 Hörsaal 3, Währinger Straße 29 3.OG
- Tuesday 04.03. 13:15 - 14:45 Seminarraum 6, Währinger Straße 29 1.OG
- Monday 10.03. 16:45 - 18:15 Hörsaal 3, Währinger Straße 29 3.OG
- Tuesday 11.03. 13:15 - 14:45 Seminarraum 6, Währinger Straße 29 1.OG
- Monday 17.03. 16:45 - 18:15 Digital
- Tuesday 18.03. 13:15 - 14:45 Digital
- Monday 24.03. 16:45 - 18:15 Hörsaal 3, Währinger Straße 29 3.OG
- Tuesday 25.03. 13:15 - 14:45 Seminarraum 6, Währinger Straße 29 1.OG
- Monday 31.03. 16:45 - 18:15 Hörsaal 3, Währinger Straße 29 3.OG
- Tuesday 01.04. 13:15 - 14:45 Seminarraum 6, Währinger Straße 29 1.OG
- Monday 07.04. 16:45 - 18:15 Hörsaal 3, Währinger Straße 29 3.OG
- Tuesday 08.04. 13:15 - 14:45 Seminarraum 6, Währinger Straße 29 1.OG
- Monday 28.04. 16:45 - 18:15 Hörsaal 3, Währinger Straße 29 3.OG
- Tuesday 29.04. 13:15 - 14:45 Seminarraum 6, Währinger Straße 29 1.OG
- Monday 05.05. 16:45 - 18:15 Hörsaal 3, Währinger Straße 29 3.OG
- Tuesday 06.05. 13:15 - 14:45 Seminarraum 6, Währinger Straße 29 1.OG
- Monday 12.05. 16:45 - 18:15 Hörsaal 3, Währinger Straße 29 3.OG
- Tuesday 13.05. 13:15 - 14:45 Seminarraum 6, Währinger Straße 29 1.OG
- Monday 19.05. 16:45 - 18:15 Hörsaal 3, Währinger Straße 29 3.OG
- Tuesday 20.05. 13:15 - 14:45 Seminarraum 6, Währinger Straße 29 1.OG
- Monday 26.05. 16:45 - 18:15 Hörsaal 3, Währinger Straße 29 3.OG
- Tuesday 27.05. 13:15 - 14:45 Seminarraum 6, Währinger Straße 29 1.OG
- Monday 02.06. 16:45 - 18:15 Hörsaal 3, Währinger Straße 29 3.OG
- Tuesday 03.06. 13:15 - 14:45 Seminarraum 6, Währinger Straße 29 1.OG
- Tuesday 10.06. 13:15 - 14:45 Seminarraum 6, Währinger Straße 29 1.OG
- N Monday 16.06. 16:45 - 18:15 Hörsaal 3, Währinger Straße 29 3.OG
- Tuesday 17.06. 13:15 - 14:45 Seminarraum 6, Währinger Straße 29 1.OG
- Monday 23.06. 16:45 - 18:15 Hörsaal 3, Währinger Straße 29 3.OG
- Tuesday 24.06. 13:15 - 14:45 Seminarraum 6, Währinger Straße 29 1.OG
- Monday 30.06. 16:45 - 18:15 Hörsaal 3, Währinger Straße 29 3.OG
Information
Aims, contents and method of the course
Assessment and permitted materials
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 exercisesPresence 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.
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 exercisesPresence 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.
Minimum requirements and assessment criteria
>= 89%, grade 1
>= 76%, grade 2
>= 63%, grade 3
>= 50%, grade 4
< 50%, grade 5
>= 76%, grade 2
>= 63%, grade 3
>= 50%, grade 4
< 50%, grade 5
Examination topics
All topics covered in class, the reading material, the exercises, and the quizzes.
Reading list
- 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.
Association in the course directory
Module: DPA
Last modified: We 12.03.2025 13:05
- 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, connectivityAt 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