Theory of Computation
Computational models for sequential algorithms. Turing machine. Random access machine (RAM). The class of polynomial problems. Algorithms on graphs. Shortest path. Minimum spanning tree. Biconnectivity-Strongly connected components. Maximum flow. The class of non-deterministically polynomial (NP) problems. Polynomial reductions. NP-complete problems. Parallel algorithms. Computational models for parallel algorithms. Interconnection networks. The parallel random access machine (PRAM). The class NC. log-space reductions. P-compete problems. Efficient and optimal parallel algorithms.