Introduction to parallel computational models (PRAM, Meshes, Trees, Hypercubes,
Shuffle-Exchange, Mesh-of-Trees) and complexity measures. Parallel algorithms design
techniques: divide-and-conquer, parallel prefix, pointer jumping, list ranking, Euler’s
path technique, and ear decomposition. Parallel algorithms for selection, merging,
sorting, searching, and graph problems. Computational geometry. Graph embedding. Parallel computational complexity: equivalence of Boolean circuits and the PRAM
models, the NC class, and P-complete problems.​