CSE350

Course CSE350
Title Theory of Computation: Honors
Credits 4
Course Coordinator

Michael Bender

Description

Introduces the abstract notions of machine computation for honors students. Includes finite automata, regular expressions, and formal languages, with emphasis on regular and context-free grammars. Explores what can and cannot be computed by considering various models of computation including Turing machines, recursive functions, and universal machines

Prerequisite CSE 150; AMS 210 or MAT 211; CSE Honors Program or Honors College or WISE
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.
  • Understanding of the power and inherent limitations of algorithmic computation.

Textbook

Harry R. Lewis and Christos H. Papadimitriou, Elements of the theory of computation, Prentice Hall. (Second Edition, 1998).

Major Topics Covered in Course
  • Strings and languages
  • Regular languages, regular expressions and finite automata
  • Turing machines, unrestricted grammars, Church-Turing thesis
  • Introduction to recursion theory, universal Turing machine, halting problem, undecidability
  • Probabilistic computation
  • Applications to operating systems, programming languages, and other areas will be discussed throughout the semester

Laboratory Projects

No large scale projects are required.

Course Webpage

CSE350