Motivation, PRAM models: CRCW, CREW, EREW PRAM
Balanced binary tree approach
Work-optimal parallel algorithms
Paralllel binary search , merging, minimum in an array
Accelerated cascading
Parallel list ranking
Pointer jumping, application to tree algorithms
Euler Tour, Tree traversals
Rooting a tree
Parallel tree BFS, distance from root
Arithmetic expression evaluation , Raking
Lowest common ancestor in trees
Applications of LCA: range minima
Work-optimal algorithm for range minima
Insem 1
Paralllel graph algorithms: connected components
Minimum spanning tree: Parallelization of Prim's algorithm
Transitive closure and all pairs shortest paths
Brent's theorem
Parallel complexity: NC, P-hard and P-complete problems
Boolean circuit value problem, NOR-CVP
Introduction to dsitributed algorithms, Motivation
Graph coloring
Coloring of paths: Local maxima algorithm
Color reduction using unique IDs
Randomized coloring in bounded degree graphs
Coloring: Reduction from q^2 colors to q colors
Port-numbering (PN) model : 3-approximate vertex cover and maximal matching
Insem 2
Local model : Graph coloring
CONGEST model: Shortest paths
Limitations of PN: Principle of locality
2-coloring requires at least Omega(n) many rounds.
Round elimination
Hardness of graph coloring, Sinkless orientation
Ref:
(JJ) An introduction to Parallel Algorithms by Joseph Jaja
(JS) Distributed Algorithms by Jukka Suomela