CS 373
CS 373 - Theory of Computation
Spring 2014
| Title | Rubric | Section | CRN | Type | Hours | Times | Days | Location | Instructor |
|---|---|---|---|---|---|---|---|---|---|
| Theory of Computation | CS373 | AD1 | 50145 | DIS | 0 | 1100 - 1150 | W | 1111 Siebel Center for Comp Sci | Jose Meseguer |
| Theory of Computation | CS373 | AD2 | 50146 | DIS | 0 | 1200 - 1250 | W | 1214 Siebel Center for Comp Sci | Jose Meseguer |
| Theory of Computation | CS373 | AD3 | 50147 | DIS | 0 | 1300 - 1350 | W | 1111 Siebel Center for Comp Sci | Jose Meseguer |
| Theory of Computation | CS373 | AD4 | 50148 | DIS | 0 | 1400 - 1450 | W | 1111 Siebel Center for Comp Sci | Jose Meseguer |
| Theory of Computation | CS373 | AD5 | 52356 | DIS | 0 | 1500 - 1550 | W | 1111 Siebel Center for Comp Sci | Jose Meseguer |
| Theory of Computation | CS373 | AD6 | 59427 | DIS | 0 | 1600 - 1650 | W | 1111 Siebel Center for Comp Sci | Jose Meseguer |
| Theory of Computation | CS373 | AL1 | 50142 | LEC | 3 | 0930 - 1045 | W F | 1404 Siebel Center for Comp Sci | Jose Meseguer Kavya Kannan |
See full schedule from Course Explorer
Official Description
Course Director
Learning Goals
Understand and reason about differences, capabilities, and limitations, of various models of computation (a), (b), (j)
Argue rigorously about whether or not a model of computation can achieve a certain task (a), (b), (j)
Understand the ultimate limits of what can be computed by any reasonable computing device (a), (b), (j)
Understand and make use of nondeterminism in the design, expression, and modeling of computation (a), (b), (j)
Be able to apply inductive proofs about computation and computational models (a)
explain how various models of computation are used in real-world problems
Topic List
Regular languages, finite automata, and regular expressions
Context-free languages, CFGs, PDAs
Turing machines, recursive and recursively enumerable sets, undecidability, and reductions
Required, Elective, or Selected Elective
Required.