Formal languages and expressiveness. Turing completeness and Church's Thesis. Decidability and tractability. Complexity classes and theory of NP completeness. Prerequisites: CS 064 or MATH 052. Co-requisite: CS 124.
Prereqs enforced by the system: CS 064 or MATH 052; Open to degree and CDE students; Common midterm on Oct 11 in Billings LH 6:40-7:55.
This course examines the question "what is computable?". We will examine increasingly complex mathematical machines for computation, ending with the equivalent of the modern computer. Along the way, we will learn about simpler computational models that can be used to efficiently model behavior, parse regular expressions, and define and parse programming language syntax.
Weekly homeworks, periodic exams.
Votey Bldg 254 (View Campus Map)
to on Tuesday and Thursday
Billings - Ira Allen Lh Lh (View Campus Map)
to on Wednesday