CS 646: Parallel Algorithms

Course Contents:

Complexity measure for a parallel algorithms.

Parallel combinatorial algorithms: permutations with and without repetitions combinations, derangements. Parallel searching algorithms: maximum/minimum, median, K-th largest/smallest element. Parallel sorting algorithms.

Parallel graph algorithms: parallel graph search &, tree traversal algorithms, parallel algorithms for connectivity problems, parallel algorithms for path problems.

Books and References:

Joseph Jaja.An Introduction to Parallel Algorithms, Addison Wesley, 1992.

H. Sparkias and A. Gibbon.Lecture notes on Parallel Computation, Cambridge University Press, 1993.

K. Hwang and F. A. Briggs.Computer Architecture and Parallel Processing, McGraw Hill Inc., 1985.

S. Akl.Design and Analysis of Parallel Algorithms, Prentice Hall Inc, 1992.

Research papers.