Jul 12, 2024  
2022-23 Undergraduate Catalog 
2022-23 Undergraduate Catalog [ARCHIVED CATALOG]

CS 4423 - Computability and Complexity Theory (3) SP

Rigorous introduction to theoretical foundations of computer science, addressing a number of interrelated topics and formally defining a computer, an algorithm and what is computable. Close reading of important theorems and proofs. Significant use of mathematical lemmas, corollaries, logical reasoning, inductive proofs, are used to introduce how to reason precisely about computation and prove mathematical theorems of computation such as Turing machines, undecidability, and computational complexity.

Prerequisite: CS 3623  with grades of “C” or higher.