Syllabus
This lecture is an introduction into parallel algorithms for the so-called massively parallel models of computers (the number of processors is a function of the input size) with shared memory.
Parallel RAM, complexity measures for parallel computations, parallel thesis.
Techniques of parallel algorithms (balanced binary trees, divide-and-conquer method, tasks splitting, cascade acceleration).
Parallel algorithms for graphs - Euler tour technique, connected components, minimal spanning tree, shortest paths.
Optimal parallel sorting, parallel merging, minimal element.
Lower bounds for parallel computations, computing OR, summation.
Polylog-complexity classes P-complete problems.
Annotation
An introductory course on parallelism devoted to theoretical models of the so-called massively parallel computations and their relation to sequential computations, basic techniques used in parallel algorithm design and hard parallelisable problems.