Designation: Required Course
Course Level: Graduate
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.