# CSE 664 Advanced Algorithms (3 Credits)

## Catalog description:

A review 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.

## Prerequisites:

An undergraduate algorithms course

## Course Objectives:

- To recognize the most well-known NP-complete problems, and categories of NP-complete problems.
- To perform the most well-known poly-time reductions between NP-hard problems, and able to extend these proofs to similar problems.
- To be able to perform the most well-known poly-time reductions between NP-hard problems, and able to extend these proofs to similar problems.
- To understand the definitions of 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.
- To understand 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.
- To analyze the performance characteristics of randomized algorithms, and adapt a randomized algorithm for a canonical problem to work on another similar problem.