Mar 28, 2024  
2018-19 Catalog 
    
2018-19 Catalog [ARCHIVED CATALOG]

Add to Favorites (opens a new window)

CS 420 - Theory of Computation


5

This course introduces students to the mathematical foundations of computation and complexity for problem-solving, including the concepts of automata theory, the theory of formal languages and grammars, and the notions of algorithm, decidability, complexity, and computability. Students will develop the ability to understand and conduct mathematical proofs for computation and algorithms in order to solve problems efficiently. 54

Prerequisite(s): MATH 301   and admission to Computer Science, BS   program, or instructor’s permission.

Course Outcomes
  • Characterize formal models of computation, such as finite automata, pushdown automata, and Turing machine and regular expressions
  • Design grammars for context-free languages
  • Classify regular and context-free languages based on their properties
  • Design Turing Machines for problems
  • Prove decidability and undecidability of languages
  • Describe class-based resource usage models, including time complexity
  • Apply basic concepts to explain the implications of modern complexity theory approaches to problem-solving


Find out when this course is offered




Add to Favorites (opens a new window)