About CS 125 B

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

Section URL

Section Description

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. Recommended co-requisite: CS 124. Linear Algebra (MATH 122/124) is also recommended, as a co-requisite or prerequisite.

Section Expectation

Required Materials: "Introduction to the Theory of Computation", Third Edition, by Michael Sipser Class participation is mandatory, and will be necessary for you to achieve a good grade in the course. The class will be delivered in Hybrid format - You are expected to watch couple of 10 minute videos every week, before attending the lecture sessions. Students who successfully complete this course will become familiar with general concepts in the theory of computer science, gain an understanding of the concepts of automata and languages, and computability theory

Evaluation

Homework Sets (5): 30% Weekly Online Quiz (10): 10% Activities (10): 10% Midterm Exam: 25% Final Exam: 25%

Course Dates

to

Location

Innovation Hall E204 (View Campus Map)

Times

to on Tuesday and Thursday

Important Dates

Note: These dates may not be accurate for select courses during the Summer Session.

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

Deadlines
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

    There are no courses that meet this criteria.