Study problems in computer science for which we have no known efficient solutions, and the methods used to recognize intractable problems as well as the current approaches taken to cope with those problems. Concept of NP-completeness and poly-time reductions; an introduction to randomized algorithms and the randomized complexity classes PP, RP, and BPP; an introduction to approximation algorithms for solving NP-Hard problems; polynomial-space algorithms and the classes PSPACE and the poly-time hierarchy; Poly-time approximation schemes and approximation algorithms via linear-program rounding.
Prerequisite:
CSE 374
Required topics (approximate weeks allocated):
Algorithms and mathematical methods of algorithm analysis (3)
Review of algorithmic complexity
Technique for proving algorithmic complexity Dynamic programming, divide and conquer, and greedy algorithms
Analyze recursive and non-recursive algorithms to determine their important computational properties.
Describe and prove properties of problems that are unlikely to have an efficient solution.
Describe the complexity classes P, NP, co-NP, RP, PP, BPP, PSPACE, and the poly-time hierarchy, and be able to prove the relationships between them.
Describe the purpose of approximation algorithms and polynomial-time approximation schemes, be able to derive the approximation factors for well-known examples, and adapt a poly-time approximation algorithm for one problem to another similar problem.
Analyze the performance characteristics of randomized algorithms, and adapt a randomized algorithm for a canonical problem to work on another similar problem.
(Graduate students only) Use the algorithms literature to synthesize new artifacts such as a working implementation and/or a technical paper.
Department of Computer Science and Software Engineering
