Sep 27, 2022  
2021-2022 Undergraduate Catalog 
2021-2022 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.

Prerequisites: CS 2233  and CS 3623  with grades of “C” or higher.