Nov 29, 2021  
Loyola Marymount University Bulletin 2021-2022 
    
Loyola Marymount University Bulletin 2021-2022

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.