CS 742: Parallel Complexity and Sub-Logarithmic Time Algorithms

Course Contents:

VLSI theory of complexity. Theory of log-space completeness. Structure of NC. Unbounded fan-in circuits. CRAM model and allocated PRAM models.

Sub-logarithmic time algorithms for Parallel symmetry breaking, parallel prefix computation, ordered chaining, nearest largers, Delaunay triangulation and convex hull.

Optimal NC algorithms for deterministic list ranking triconnectivity and task Scheduling.

Books and References:

1. J. D. Ullman.Computational Aspects of VLSI, Computer Science Press, 1984.
2. F. P. Preparata.Advances in Computing Research, Vol II: VLSI Theory, Jai Press, England, 1984.
3. Research papers.