Introduction: data structures, algorithms, correctness criteria, non-existence result. Complexity classes – L, NL, P, NP, PSPACE, EXPTIME, EXPSPACE, DECIDABLE, UNDECIDABLE. The class P, and examples of analysis of worst- and expected-case efficiency. Optimization vs. decision problems, the class NP, Cooke and Karp reductions, the polynomial hierarchy. Recognizing optimal substructure, dynamic programming, when not to be naive. Reconciling NP- completeness – NP as an upper-bound, reduction to SAT and SAT solvers. Reconciling PSPACE- completeness – model checking, PSPACE as an upper-bound. The...
Read more about (TA) ECE 606 Algorithms