View Fall 2017 Courses

Computer Science: QR: Computability& Complexity

CS 125 A (CRN: 92053)

3 Credit Hours

About CS 125 A

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.

Notes

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.

Section Description

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.

Evaluation

Weekly homeworks, periodic exams.

Meetings

to

Location

Votey Bldg 254 (View Campus Map)

Times

to on Tuesday and Thursday

Location

Billings - Ira Allen Lh Lh (View Campus Map)

Times

to on Wednesday