Advanced Parallel Algorithms
Code  Completion  Credits  Range 

PIPPA  ZK  4  3C 
 Lecturer:
 Tutor:
 Pavel Tvrdík (guarantor)
 Supervisor:
 Department of Computer Systems
 Synopsis:

The students learn complex parallel algorithms and techniques to assess their correctness efficiency and optimality.
 Requirements:

MIEPAR
 Syllabus of lectures:

1. PRAM algorithms for generalized prefix sum on arrays and their applications.
2. PRAM deterministic algorithms for prefix computations on lists.
3. PRAM algorithms for tree contraction and expression evaluation.
4. PRAM deterministic algorithms for computation of connected graph components.
5. PRAM randomized algorithms for computation of connected graph components.
6. PRAM deterministic optimal sorting.
7. Optimal ordering on meshes.
8. Parallel algorithms for computational geometry.
9. Parallel algebraic algorithms.
10. Parallel complexity, P and NC complexity classes..
 Syllabus of tutorials:
 Study Objective:

To explain the advanced techniques that are extensively used for designing fundamental parallel efficient algorithms for solving problems. These techniques go beyond the usual paradigm of data parallelism combined with reductions and prefix sums. Besides explanations of the ideas behind these nontrivial techniques, students learn sophisticated procedures for complexity, efficiency, and optimality analysis of these algorithms. The algorithms are PRAM  or meshbased.
 Study materials:

J. H. Reif, ed. Synthesis of parallel algorithms, Morgan Kaufmann Publ., 1993, ISBN 155860135X
J. Ja'Ja'. An introduction to parallel algorithms. AddisonWesley. 1992.
 Note:
 Timetable for winter semester 2020/2021:
 Timetable is not available yet
 Timetable for summer semester 2020/2021:
 Timetable is not available yet
 The course is a part of the following study plans:

 Informatics (doctoral) (compulsory elective course)
 Informatics (compulsory elective course)