CP7013 DESIGN AND ANALYSIS OF PARALLEL ALGORITHMS

CP7013      DESIGN AND ANALYSIS OF PARALLEL ALGORITHMS

UNIT I           INTRODUCTION

 Introduction to Parallel Algorithms – Models of Parallel Computation – Sorting on an EREW-SIMD PRAM Computer – Relation between PRAM Models – SIMD Algorithms – MIMD Algorithms – Selection – Desirable Properties for Parallel Algorithms - Parallel Algorithm for Selection – Analysis of Parallel Algorithms.  

UNIT II        SORTING AND SEARCHING

 Merging on the EREW and CREW Models - Fast Merging on EREW - Sorting Networks – Sorting on a Linear Array – Sorting on CRCW, CREW, EREW Models – Searching a Sorted Sequence – Searching a Random Sequence.

UNIT III         ALGEBRAIC PROBLEMS

Generating Permutations and Combinations in Parallel – Matrix Transpositions – Matrix by Matrix Multiplications – Matrix by Vector multiplication.   

UNIT IV        GRAPH THEORY AND COMPUTATIONAL GEOMETRY PROBLEMS

Connectivity Matrix – Connected Components – All Pairs Shortest Paths – Minimum Spanning Trees – Point Inclusion – Intersection, Proximity and Construction Problems - Sequential Tree Traversal - Basic Design Principles – Algorithm – Analysis.  

UNITV         DECISION AND OPTIMIZATION PROBLEMS

 Computing Prefix Sums – Applications - Job Sequencing with Deadlines – Knapsack Problem- The Bit Complexity of Parallel Computations. 

REFERENCES: 

1. Selim G. Akl, “The Design and Analysis of Parallel Algorithms”, Prentice Hall, New Jersey, 1989. 2. Michael J. Quinn, “Parallel Computing : Theory & Practice”, Tata McGraw Hill Edition, 2003. 

3. Justin R. Smith, “The Design and Analysis of Parallel Algorithms”, Oxford University Press, USA , 1993. 4. Joseph JaJa, “Introduction to Parallel Algorithms”, Addison-Wesley, 1992.