Course Websites
CS 373 - Theory of Computation
Last offered Spring 2014
Official Description
Related Faculty
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
Assessment and Revisions
Revisions in last 6 years | Approximately when revision was done | Reason for revision | Data or documentation available? |
Greater emphasis on mathematical proofs since the course was moved earlier in the program. Some topics were dropped: complexity theory; some topics in context-free languages related to Greibach Normal Form, PDA-CFG equivalence, and deterministic CFLs; some harder problems in homework/lecture were removed. | Fall 2006 | The earlier course (CS 375/475) was optional in the curriculum. As a consequence, some undergraduate students were never exposed to formal models of computation like Turing machines. Also, CS 421 (Programming Languages and Compilers) had to introduce regular languages, and context-free languages. The theory group felt these issues could be addressed by making the class mandatory, and a pre-requisite for CS 421 and CS 473 (Algorithms). The course was, therefore, changed to make it more accessible to sophmores and juniors. | No documentation but the theory group had multiple meetings to discuss the contents of all theory classes. |
Required, Elective, or Selected Elective
Required.
Title | Section | CRN | Type | Hours | Times | Days | Location | Instructor |
---|---|---|---|---|---|---|---|---|
Theory of Computation | AD1 | 50145 | DIS | 0 | 1100 - 1150 | W | 1111 Siebel Center for Comp Sci | Jose Meseguer |
Theory of Computation | AD2 | 50146 | DIS | 0 | 1200 - 1250 | W | 1214 Siebel Center for Comp Sci | Jose Meseguer |
Theory of Computation | AD3 | 50147 | DIS | 0 | 1300 - 1350 | W | 1111 Siebel Center for Comp Sci | Jose Meseguer |
Theory of Computation | AD4 | 50148 | DIS | 0 | 1400 - 1450 | W | 1111 Siebel Center for Comp Sci | Jose Meseguer |
Theory of Computation | AD5 | 52356 | DIS | 0 | 1500 - 1550 | W | 1111 Siebel Center for Comp Sci | Jose Meseguer |
Theory of Computation | AD6 | 59427 | DIS | 0 | 1600 - 1650 | W | 1111 Siebel Center for Comp Sci | Jose Meseguer |
Theory of Computation | AL1 | 50142 | LEC | 3 | 0930 - 1045 | W F | 1404 Siebel Center for Comp Sci | Jose Meseguer Kavya Kannan |