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

Bulletin Link
Prerequisite

CSE150 or CSE215; AMS 210 or MAT 211; Computer Science Honors Program or Honors College or the WISE Honors program or University Scholar
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

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

 

Undergraduate Programs