CMSI 583 Computability and Complexity

3 semester hours

Introduction to the study of computability and computational complexity. Models for computation such as finite automata, pushdown automata, Turing machines, Post canonical systems, partial recursive functions, and phrase structure grammars. Complexity classes such as P, NP, RP, and NC. NP- Completeness. Efficient algorithms for matrix multiplication and fast Fourier transforms. Approximation algorithms, randomized algorithms and parallel algorithms.