| Course Code: CS501 Course Name: Parallel Algorithm Prerequisites: 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. |