Logo ČVUT
CZECH TECHNICAL UNIVERSITY IN PRAGUE
STUDY PLANS
2018/2019

Advanced Parallel Algorithms

Login to KOS for course enrollment Display time-table
Code Completion Credits Range
PI-PPA ZK 4 0+3
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:

MIE-PAR

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 mesh-based.

Study materials:

J. H. Reif, ed. Synthesis of parallel algorithms, Morgan Kaufmann Publ., 1993, ISBN 1-55860-135-X

J. Ja'Ja'. An introduction to parallel algorithms. Addison-Wesley. 1992.

Note:
Time-table for winter semester 2018/2019:
Time-table is not available yet
Time-table for summer semester 2018/2019:
Time-table is not available yet
The course is a part of the following study plans:
Data valid to 2019-05-19
For updated information see http://bilakniha.cvut.cz/en/predmet1601706.html