Schedule

Instructors: Abhijit Das and Swagato Sanyal
Timing: Slot V3 [Thu (03:00pm–05:00pm), Fri (03:00pm–04:00pm)]
Classroom: CSE 107
Teaching Assistant: Sayani Sinha

Notices and Announcements

July 20, 2023 [for prospective registrants]

For the prerequisites of this course, please consult ERP. For us, it is very desirable that students registering for this course have completed a basic algorithms course in undergraduate/graduate level. If ERP demands other prerequisites (which you do not have), please let us know.

This is an Algorithms Course. This course is not meant for covering parallel programming. If you are interested to know about various parallel programming techniques, register for the course High Performance Parallel Programming offered in Spring semesters. For learning distributed algorithms, register for the course Distributed Systems also offered in Spring semesters.

Tentative Coverage

• 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.
• Parallel Complexity: Lower bounds for PRAM models, the complexity class NC, P-completeness.

Books and References

The main textbook will be:

• Joseph F Jájá, An Introduction to Parallel Algorithms, Addison-Wesley, 1992.

Some other references are:

• 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.

Test Schedule (Tentative)

• Class Test 1: 13-Sep-2023 [Questions with solutions]
• Class Test 2: 08-Nov-2023 [Questions with solutions]
• Mid-semester Test: 26-Sep-2023 [Questions with solutions]
• End-semester Test: 24-Nov-2023 [Questions with solutions]

Earlier semesters: Autumn 2018 | Autumn 2017