CSE 484/584 Algorithms II

Catalog description:

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

Graduate Students:

Students taking the course for graduate credit will:

  1. Conduct independent research on an algorithms topic that is not covered in the class.
  2. Analyze algorithms, develop proofs, and implement algorithms at a level of sophistication that is more than what is expected of undergraduate students.

Course Outcomes:

  1. Analyze recursive and non-recursive algorithms to determine their important computational properties.
  2. Describe and prove properties of problems that are unlikely to have an efficient solution.
  3. 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.
  4. 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.
  5. Analyze the performance characteristics of randomized algorithms, and adapt a randomized algorithm for a canonical problem to work on another similar problem.
  6. (Graduate students only) Use the algorithms literature to synthesize new artifacts such as a working implementation and/or a technical paper.