Schedule

Instructor: Abhijit Das
Timing: Slot G3 [Wed (11:00–11:55), Thu (12:00–12:55), Fri (08:00–08:55)]
Classroom: CSE 107
Teaching Assistants: Rahul Upadhya and Souvik Sur

Notices and Announcements

June 21, 2017, 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.
• Algorithms for PRAM Models: Balancing, divide and conquer, parallel prefix computation, pointer jumping, symmetry breaking, list ranking, sorting and searching, 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: 15-Nov-2017 [Questions with solutions]
• Mid-semester test: 19-Sep-2017 [Questions with solutions]
• End-semester test: 22-Nov-2017 [Questions with solutions]