CS 2250 B (CRN: 13061)

Computer Science: Computability& Complexity (B)

3 credit hours

About CS 2250 B

Formal languages and expressiveness. Turing completeness and Church's Thesis. Decidability and tractability. Complexity classes and theory of NP completeness. Prerequisites: CS 1640 or MATH 2055. Co-requisite: CS 2240.

Notes

Prereqs enforced by the system: CS 1640 or MATH 2055; Coreq: CS 2240; Open to Degree and PACE students

Section Description

In this course, we will explore the mathematical models of computation that we use to reason about computers and their capabilities. Finite automata, context-free grammars, and Turing machines each recognize (or compute) a different category of formal languages (i.e. problems), and we will dive into these differences to understand the limits of each model. At the end of the course, we will introduce runtime complexity in the context of Turing machines.

Evaluation

Weekly quizzes, exams (3), homework (5 or 6), weekly active learning exercises.

Important Dates

Courses may be cancelled due to low enrollment. Show your interest by enrolling.

Last Day to Add
Last Day to Drop
Last Day to Withdraw with 50% Refund
Last Day to Withdraw with 25% Refund
Last Day to Withdraw

Resources

Other Sections