CSE 396 : Introduction To The Theory Of Computation
Credits: 4
Semester: F
Prerequisites: CSE 250
Corequisites: None
Type: LEC/REC
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.
Class Schedule: Fall 2009
CSE 396 not offered in this semester, or the department has chosen not to publish it in the on-line class schedule.
Class Schedule: Spring 2010
| 4 Course(s) | ||||||||||||||||||||
| Reg # | Course | Title | Section | Type | Days | Time | Room | Location | Instructor | Status | ||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 107359 | CSE 396 | Intro Theory Of Computatn | R 1 | REC | M | 8:00 AM - 8:50 AM | 209 NORTON | North | Staff | Open | ||||||||||
| 345346 | CSE 396 | Intro Theory Of Computatn | R 2 | REC | R | 4:00 PM - 4:50 PM | 112 BALDY | North | Staff | Closed | ||||||||||
| 397382 | CSE 396 | Intro Theory Of Computatn | R 3 | REC | T | 1:00 PM - 1:50 PM | 214 NORTON | North | Staff | Open | ||||||||||
| <<< >>> | CSE 396 | Intro Theory Of Computatn | LEC | M W | 4:00 PM - 5:20 PM | 112 OBRIAN | North | Regan, K W | Open | |||||||||||
Last Updated: Nov 24, 2009 7:54:03 AM
