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


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 to Distributed Algorithms, so I will not cover these. Students who are interested in learning parallel and/or distributed programming tools should take the course High 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


Autumn 17 | Home