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.

CSE 374

- 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

- NP-completeness (3)
- Polynomial time
- Polynomial-time verification
- NP-completeness and reducibility
- NP-completeness proofs
- NP-completeness problems
- Well-known NP-complete problems.

- Other complexity classes (2)
- Approximation algorithms (3)
- Randomized algorithms (2)
- Exams (1)

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

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