CS501 | PARALLEL ALGORITHM | 3-0-0-6 |
Pre-requisites : CS204 |
Syllabus : 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. |
Texts : 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. |
References : 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. |