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	Prerequisites: CSE 113 or CSE 150 or CSE 215; AMS 210 or MAT 211; Honors in Computer Science or the Honors College or the WISE Honors Program or University Scholars or the Simons STEM Scholars Program.
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	No large scale projects are required.
Course Webpage	CSE350