Skip to main content.

Courses

Subjects

Search Results

Course Prefix: CSE   Course #: 396   Keywords: null   showing 1 to 1 of ~1

CSE 396LR Introduction to the Theory of Computation

View Schedule CSE 396LR Introduction to the Theory of Computation Lecture

Covers machine models and formal specifications of the classes of computational problems they can solve. The central concepts are the Turing machine and the classes of decidable and computably enumerable languages. The Halting Problem and other natural problems are shown to be undecidable by Turing machines, implying that they are undecidable by high-level programming languages or any other known computational model. Finite automata, which are Turing machines without external memory, are shown to correspond to the class of regular languages. The course also covers regular expressions, time and space complexity of Turing machines, reducibility between problems, and NP-completeness.

Credits: 4
Grading: Graded (GRD)
Typically Offered: Spring
Prerequisites: CSE 191 or MTH 311 and CSE 250, and MTH 142. Approved Computer Science, Computer Engineering, Bioinformatics/CS Majors Only.

Course Search

date_range Schedule: {{course.abbr}} {{course.num}} {{course.title}} close
 
No schedule for this course in the {{semester.toUpperCase()}} semester.
Schedule for {{course.abbr}} {{course.num}} {{course.title}}
Course # Type Title Section Where When Seats Left
{{c._id}} << >> {{c.catalog.type_pk}} {{c.alt_title}} {{c.catalog.description}} {{c.section}} {{c.room}} MTWRFSaSu {{getTime(c.when[0].dates.start,false)}}-{{getTime(c.when[0].dates.end,true)}} {{getSeatsLeft(c.enrollment)}}
 
Published: Jul 23, 2019 14:26:04