CSc 48600 - Introduction to Computational Complexity


An introduction to the performance and limitations of computer algorithms through a study of selected algorithms. Topics include primality testing and integer factorization, algorithms for integer programming and knapsack problems, reductions and NP-completeness, randomized algorithms, and experimental algorithms arising from new technologies such as molecular, neural, and quantum computing.

Prereq.: CSc 21700, CSc 30400. 3 hr./wk.; 3 cr.