052114 VU Distributed and Parallel Algorithms (2024S)
Prüfungsimmanente Lehrveranstaltung
Labels
An/Abmeldung
Hinweis: Ihr Anmeldezeitpunkt innerhalb der Frist hat keine Auswirkungen auf die Platzvergabe (kein "first come, first served").
- Anmeldung von Mo 12.02.2024 09:00 bis Do 22.02.2024 09:00
- Abmeldung bis Do 14.03.2024 23:59
Details
max. 25 Teilnehmer*innen
Sprache: Englisch
Lehrende
Termine (iCal) - nächster Termin ist mit N markiert
Montag
04.03.
16:45 - 18:15
Hörsaal 2, Währinger Straße 29 2.OG
Dienstag
05.03.
13:15 - 14:45
Seminarraum 6, Währinger Straße 29 1.OG
Montag
11.03.
16:45 - 18:15
Hörsaal 3, Währinger Straße 29 3.OG
Montag
18.03.
16:45 - 18:15
Hörsaal 3, Währinger Straße 29 3.OG
Dienstag
19.03.
13:15 - 14:45
Seminarraum 6, Währinger Straße 29 1.OG
Montag
08.04.
16:45 - 18:15
Hörsaal 3, Währinger Straße 29 3.OG
Dienstag
09.04.
13:15 - 14:45
Seminarraum 6, Währinger Straße 29 1.OG
Montag
15.04.
16:45 - 18:15
Hörsaal 3, Währinger Straße 29 3.OG
Dienstag
16.04.
13:15 - 14:45
Seminarraum 6, Währinger Straße 29 1.OG
Montag
22.04.
16:45 - 18:15
Hörsaal 3, Währinger Straße 29 3.OG
Dienstag
23.04.
13:15 - 14:45
Seminarraum 6, Währinger Straße 29 1.OG
Montag
29.04.
16:45 - 18:15
Hörsaal 3, Währinger Straße 29 3.OG
Dienstag
30.04.
13:15 - 14:45
Seminarraum 6, Währinger Straße 29 1.OG
N
Montag
06.05.
16:45 - 18:15
Hörsaal 3, Währinger Straße 29 3.OG
Dienstag
07.05.
13:15 - 14:45
Seminarraum 6, Währinger Straße 29 1.OG
Montag
13.05.
16:45 - 18:15
Hörsaal 3, Währinger Straße 29 3.OG
Dienstag
14.05.
13:15 - 14:45
Seminarraum 6, Währinger Straße 29 1.OG
Dienstag
21.05.
13:15 - 14:45
Seminarraum 6, Währinger Straße 29 1.OG
Montag
27.05.
16:45 - 18:15
Hörsaal 3, Währinger Straße 29 3.OG
Dienstag
28.05.
13:15 - 14:45
Seminarraum 6, Währinger Straße 29 1.OG
Montag
03.06.
16:45 - 18:15
Hörsaal 3, Währinger Straße 29 3.OG
Dienstag
04.06.
13:15 - 14:45
Seminarraum 6, Währinger Straße 29 1.OG
Montag
10.06.
16:45 - 18:15
Hörsaal 3, Währinger Straße 29 3.OG
Dienstag
11.06.
13:15 - 14:45
Seminarraum 6, Währinger Straße 29 1.OG
Montag
17.06.
16:45 - 18:15
Hörsaal 3, Währinger Straße 29 3.OG
Dienstag
18.06.
13:15 - 14:45
Seminarraum 6, Währinger Straße 29 1.OG
Montag
24.06.
16:45 - 18:15
Hörsaal 3, Währinger Straße 29 3.OG
Dienstag
25.06.
13:15 - 14:45
Seminarraum 6, Währinger Straße 29 1.OG
Information
Ziele, Inhalte und Methode der Lehrveranstaltung
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 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.
Mindestanforderungen und Beurteilungsmaßstab
>= 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
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: So 03.03.2024 19:25
- 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