CS60040/CS60026 Parallel and Distributed Algorithms |
Autumn 2018, L-T-P: 3-0-0 |

## Schedule

Instructor:Abhijit Das

Timing:Slot A3 [Mon (08:00–09:55), Tue (12:00–12:55)]

Classroom:CSE 107

Teaching Assistants:Gulab Arora and Soumadip Biswas## Notices and Announcements

July 02, 2018, for prospective registrants:- This course has no official prerequisites. However, it is desirable that students registering for this course have completed a basic algorithms course in undergraduate/graduate level.
## Tentative Coverage

This course will concentrate on the design and analysis of parallel algorithms. The CSE Department offers a course dedicated toDistributed Algorithms, so I will not cover these. Students who are interested in learning parallel and/or distributed programming tools should take the courseHigh Performance Parallel Programming.The following broad topics will be covered.

Parallel Programming Models:Shared-memory model (PRAM, MIMD, SIMD), network model (line, ring, mesh, hypercube), performance measurement of parallel algorithms.Algorithm Design Techniquess for PRAM Models:Balancing, divide and conquer, parallel prefix computation, pointer jumping, symmetry breaking, pipelining, accelerated cascading.Algorithms for PRAM Models:List ranking, sorting and searching, tree algorithms, graph algorithms, string algorithms.Algorithms for Network Models:Matrix algorithms, sorting, graph algorithms, routing, relationship with PRAM models.Parallel Complexity:Lower bounds for PRAM models, the complexity class NC, P-completeness.## Books and References

- Joseph F Jájá,
An Introduction to Parallel Algorithms, Addison-Wesley, 1992.- Michael J Quinn,
Parallel Computing: Theory and Practice, second edition, McGraw Hill, 1994/2002.- Michael J Quinn,
Parallel Programming in C with MPI and OpenMP, first edition, McGraw Hill, 2004/2003.- Ananth Grama, Anshul Gupta, George Karypis and Vipin Kumar,
Introduction to Parallel Computing, second edition, Addison-Wesley/Pearson, 1994/2003.- Russ Miller and Laurence Boxer,
Algorithms: Sequential and Parallel — A Unified Approach, third edition, Cengage, 2013.- Fayez Gebali,
Algorithms and Parallel Computing, Wiley, 2011.- Seyed H Roosta,
Parallel Processing and Parallel Algorithms: Theory and Computation, Springer, 2000.## Tests

- Class test: Questions with solutions
- Mid-semester test: Questions with solutions
- End-semester test: Questions with solutions