CSE303

Course CSE303
Title Introduction to the Theory of Computation
Credits 3
Course Coordinator

Michael Bender
Description

An introduction to the abstract notions encountered in machine computation. Topics include finite automata, regular expressions, and formal languages, with emphasis on regular and context-free grammars. Questions relating to what can and cannot be done by machines are covered by considering various models of computation, including Turing machines, recursive functions, and universal machines. Not for credit in addition to CSE 350.

Bulletin Link
Prerequisite Prerequisites: C or higher: CSE 160 or CSE 214; CSE 150 or CSE 215; CSE major
Course Outcomes
  • An ability to define and use abstract models of computation such as finite and push-down automata, and analyze their relative expressive power.
  • An ability to define, use, and convert between abstract machine models and formal languages.
  • An ability to apply abstract models of computation to analyze the power and inherent limitations of algorithms.
Textbook
  • Michael Sipser, Introduction to the Theory of Computation, Cengage Learning, 3rd ed., 2012.
  • Supplementary Material: Ding-Zhu and Ker-I Ko, Problem Solving in Automata, Languages and Complexity, Wiley.
  • Elements of the Theory of Computation, Harry R. Lewis and Christos H. Papadimitriou, Prentice Hall, Second Edition
Major Topics Covered in Course
  • Strings and languages
  • Regular languages, regular expressions and finite automata
  • Context-free grammars, parsing, pushdown automata
  • Turing machines, unrestricted grammars, Church-Turing thesis
  • Introduction to recursion theory, universal Turing machine, halting problem, undecidability
Laboratory

No large scale projects are required.
Course Webpage

CSE303