Pre-requisites : CS204
Theoretical models of parallel computation: variants of the PRAM model, interconnection networks, synchronous and asynchronous models. Performance of parallel algorithms. Basic techniques: balanced trees, recursive doubling, divide and conquer, partitioning, pipelining, accelerated cascading, symmetry breaking.List ranking, the Euler tour technique, tree contraction. Algorithms for searching, merging and sorting. Graph algorithms: Connected Components, Colouring. Parallel algorithms on interconnection networks and other architectures. Algorithms on asynchronous models. Limits to parallelizability. NC-reductions, P-completeness.
1. J. Jaja, An Introduction to Parallel Algorithms, Addison Wesley, 1992.
2. F. T. Leighton, Introduction to Parallel Algorithms and Architectures: Arrays,Trees,Hypercubes,Morgan Kaufmann Publishers,San Mateo,California,1992.
1. J. H. Reif, Synthesis of Parallel Algorithms, Morgan Kaufmann Publishers, San Mateo, California.
2. S. G. Akl, Parallel Computation: Models and Methods, Prentice Hall, 1996.