Review of RAM model of computation, complexity measures of time and space. Graph
Algorithms for minimum spanning trees, shortest paths, matroids, the planar separator
theorem. Planarity and planarization. network flow algorithms. Graph matching and
coloring. Establishing lower bounds. NP Completeness: Cook’s theorem. Various
complexity classes and their relationships. Techniques for establishing completeness.
Approximation and probabilistic algorithms to NP-hard problems.​