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.

An undergraduate algorithms course

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

Benton Hall, Room 205

650 E. High Street

Oxford, OH 45056

501 E. High Street

Oxford, OH 45056

- Campus Map
- Directions
- Online: Miami Online

- Main Operator 513-529-1809
- Office of Admission 513-529-2531
- Vine Hotline 513-529-6400
- Emergency Info https://miamioh.edu/emergency

1601 University Blvd.

Hamilton, OH 45011

- Campus Map
- Directions
- Online: E-Campus

- Main Operator 513-785-3000
- Office of Admission 513-785-3111
- Campus Status Line 513-785-3077
- Emergency Info https://miamioh.edu/regionals/emergency

4200 N. University Blvd.

Middletown, OH 45042

- Campus Map
- Directions
- Online: E-Campus

- Main Operator 513-727-3200
- Office of Admission 513-727-3216
- Campus Status 513-727-3477
- Emergency Info https://miamioh.edu/regionals/emergency

7847 VOA Park Dr.

(Corner of VOA Park Dr. and Cox Rd.)

West Chester, OH 45069

- Main Operator 513-895-8862
- From Middletown 513-217-8862
- Emergency Info https://miamioh.edu/regionals/emergency

Chateau de Differdange

1, Impasse du Chateau, L-4524 Differdange

Grand Duchy of Luxembourg

- Main Operator 011-352-582222-1
- Email luxembourg@MiamiOH.edu
- Website https://miamioh.edu/luxembourg

217-222 MacMillan Hall

501 E. Spring St.

Oxford, OH 45056, USA

- Main Operator 513-529-8600
- Emergency Info https://miamioh.edu/emergency

© 2023 Miami University All Rights Reserved