Course Websites

CS 373 - Theory of Computation

Last offered Spring 2014

Official Description

Finite automata and regular languages; pushdown automata and context-free languages; Turing machines and recursively enumerable sets; computability and the halting problem; undecidable problems. Course Information: Prerequisite: CS 173 or MATH 213; CS 225. Class Schedule Information: Students must register for one lecture and one discussion section.

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.

TitleSectionCRNTypeHoursTimesDaysLocationInstructor
Theory of ComputationAD150145DIS01100 - 1150 W  1111 Siebel Center for Comp Sci Jose Meseguer
Theory of ComputationAD250146DIS01200 - 1250 W  1214 Siebel Center for Comp Sci Jose Meseguer
Theory of ComputationAD350147DIS01300 - 1350 W  1111 Siebel Center for Comp Sci Jose Meseguer
Theory of ComputationAD450148DIS01400 - 1450 W  1111 Siebel Center for Comp Sci Jose Meseguer
Theory of ComputationAD552356DIS01500 - 1550 W  1111 Siebel Center for Comp Sci Jose Meseguer
Theory of ComputationAD659427DIS01600 - 1650 W  1111 Siebel Center for Comp Sci Jose Meseguer
Theory of ComputationAL150142LEC30930 - 1045 W F  1404 Siebel Center for Comp Sci Jose Meseguer
Kavya Kannan