X
X
X

X
Courses » Parallel Algorithms

Parallel Algorithms

ABOUT THE COURSE:

A conventional algorithm uses a single processing element. A parallel algorithm assumes that there are multiple processors. These processors may communicate with each other using a shared memory or an interconnection network. An algorithm designed for a large number (for example, a polynomial in the problem size) of processors can be simulated on a machine with a small number of processor for a trade off on time, and therefore is of practical value, while at the same time allowing us to test the limits of parallelism. Many algorithmic design techniques in the parallel setting will be explored. Parallel complexity theory will also be briefly studied.

INTENDED AUDIENCE:
BTech final year, MTech, PhD students

CORE/ELECTIVE: Elective

UG/PG: UG final year and PG

PREREQUISITES: Should have done courses in Data Structures, Algorithms and Discrete Mathematicsl

INDUSTRY SUPPORT: NA

1739 students have enrolled already!!

ABOUT THE INSTRUCTOR:



Professor Sajith Gopalan [PhD (IIT Kanpur, 1998),   MTech (IIT Kanpur, 1993), BTech (REC Calicut, 1991)] has been in the faculty of Computer Science and Engineering at IIT Guwahati since 1997. Research interests: Algorithms, Parallel Computing, Complexity Theory, Game Theory


COURSE LAYOUT:

Week 1  :  Theoretical models: PRAM, interconnection networks
Week 2  :  Performance of parallel algorithms,Basic techniques
Week 3  :  Basic techniques
Week 4  :  Comparator Networks.
Week 5  :  Optimal List ranking, applications
Week 6  :  Algorithms for searching, merging and sorting. Cole’s Merge Sort
Week 7  :  Cole’s Merge Sort(cont’d), Graph algorithms
Week 8  :  Graph algorithms (cont’d)
Week 9  :  Sorting in meshes, Hypercube algorithms, Butterfly network, CCC, Benes network
Week 10  :  Butterfly network, CCC, Benes network etc
Week 11  :  Limits to parallelizability. Lower bounds
Week 12  :  Limits to parallelizability. NC-reductions, P-completeness.

SUGGESTED READING MATERIALS:

  1. J. Jaja, An Introduction to Parallel Algorithms, Addison Wesley, 1992.
  2. F. T. Leighton, Introduction to Parallel Algorithms and Architectures: Arrays,Trees,Hypercubes,Morgan Kaufmann Publishers,San Mateo,California,1992.
CERTIFICATION EXAM :
  • The exam is optional for a fee.
  • Date and Time of Exams: April 28 2019(Sunday). Morning session 9am to 12 noon; Afternoon Session 2pm to 5pm.
  • Registration url: Announcements will be made when the registration form is open for registrations.
  • The online registration form has to be filled and the certification exam fee needs to be paid. More details will be made available when the exam registration form is published.

CERTIFICATION:

  • Final score will be calculated as : 25% assignment score + 75% final exam score
  • 25% assignment score is calculated as 25% of average of  Best 8 out of 12 assignments
  • E-Certificate will be given to those who register and write the exam and score greater than or equal to 40% final score. Certificate will have your name, photograph and the score in the final exam with the breakup.It will have the logos of NPTEL and IIT Guwahati.It will be e-verifiable at nptel.ac.in/noc.