CP7013 DESIGN AND ANALYSIS OF PARALLEL ALGORITHMS Syllabus - Anna University ME CSE 2nd Semester Regulation 2013 CP7013 Syllabus - www.annauniv.edu
OBJECTIVES:
To understand the need for parallel algorithms
To expose the students to different models of parallel computation
To expose the students to parallel sorting and searching algorithms
To understand the application of the concepts studied to different types of problems
To analyze parallel algorithms
UNIT I INTRODUCTION
Introduction to Parallel Algorithms – Models of Parallel Computation – Sorting on an EREWSIMD
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.
OUTCOMES:
Upon completion of the course, the students will be able to
Identify the need for parallel algorithms
Discuss the classification of parallel architectures and identify suitable programming models
Perform sorting on Sorting on CRCW, CREW, EREW Models
Search a sorted as well as random sequence
Develop and analyze algorithms for different applications like matrix multiplication,
shortest path, job sequencing and the knapsack problem.
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.
ADS HERE !!!