INTRODUCTION TO THEORY OF COMPUTING
Basics about the notion, capabilities, and limitations of computation: elements of finite automata and regular languages, computability theory, and computational complexity theory. Additional topics include context-free grammars and languages, and complexity-theoretic cryptography.
Topics
- context-free grammars and languages
- and complexity-theoretic cryptography
Topics explicitly listed in official catalogue description
Prerequisites & course information
Requisites: ( MATH/COMP SCI 240 or STAT/COMP SCI/MATH 475 ) and (COMP SCI 367 or 400 ), or graduate/professional standing, or declared in the Capstone Certificate in Computer Sciences for Professionals Course Designation: Core GenEd - Mathematics & Quantitative Reasoning Breadth - Natural Science Level - Advanced L&S Credit - L&S Liberal Arts and Science Repeatable for Credit: No Last Taught: Fall 2026 Learning Outcomes: 1. Design and implement deterministic finite automata to capture specified regular languages. Audience: Undergraduate 2. Differentiate between deterministic and nondeterministic finite automata and apply finite automata theory to express those computation tasks that can be captured by regular languages. Audience: Undergraduate 3. Express and interpret computational models that lead to and capture algorithmic thinking. Audience: Undergraduate 4. Design and implement a pushdown automata to capture specified context-free languages. Audience: Undergraduate 5. Identify and explain reasoning about formalization of computation, formulated as various models of computation and make transformations between finite automata and regular languages, pushdown automata and context-free languages. Audience: Undergraduate 6. Construct clear, concise, and sound proofs for statements regarding different models of computation, their relative strengths and weaknesses. Audience: Undergraduate 7. Reason with Turing machines, and the various equivalent formulations of computability theory, for example to explain how the formalization captures everyday computational processes. Audience: Undergraduate 8. Reason about computational intractability, applying the concepts of NP-hardness and NP-completeness to classify computational problems. Audience: Undergraduate Learning Outcomes: 1. Design and implement deterministic finite automata to capture specified regular languages. Audience: Undergraduate 2. Differentiate between deterministic and nondeterministic finite automata and apply finite automata theory to express those computation tasks that can be captured by regular languages. Audience: Undergraduate 3. Express and interpret computational models that lead to and capture algorithmic thinking. Audience: Undergraduate 4. Design and implement a pushdown automata to capture specified context-free languages. Audience: Undergraduate 5. Identify and explain reasoning about formalization of computation, formulated as various models of computation and make transformations between finite automata and regular languages, pushdown automata and context-free languages. Audience: Undergraduate 6. Construct clear, concise, and sound proofs for statements regarding different models of computation, their relative strengths and weaknesses. Audience: Undergraduate 7. Reason with Turing machines, and the various equivalent formulations of computability theory, for example to explain how the formalization captures everyday computational processes. Audience: Undergraduate 8. Reason about computational intractability, applying the concepts of NP-hardness and NP-completeness to classify computational problems. Audience: Undergraduate
Sources
- Course catalogue ↗2026-2027