Designation: Elective Course
Course Level: Graduate
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.