ÍÃ×ÓÏÈÉú

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

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
• 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)