Apr 23, 2024  
2021-2022 Cal State East Bay Catalog 
    
2021-2022 Cal State East Bay Catalog [ARCHIVED CATALOG]

Add to Folder (opens a new window)

CS 611 - Theory of Computation


Units: 3
Alphabets, strings and languages, regular languages and finite automata, context-free languages, grammars, context-sensitivity, Turing machines and Turing-Completeness, decidability, Church-Turing thesis, reducibility, time and space complexity classes, P versus NP, NP-Completeness and NP-Hard problems.

Prerequisites: CS 411 or M.S. Computer Science major.
Credit Restrictions: Computer Science M.S. or B.S. students only.
Equivalent Quarter Course: CS 6260.
Possible Instructional Methods: Entirely On-ground.
Grading: A-F grading only.
Student Learning Outcomes - Upon successful completion of this course students will be able to:
  1. Construct formal models of computation such as DFAs, CFGs, and Turing machines to describe various languages.
  2. Develop complex proofs to statements regarding the complexity of languages.
  3. Determine whether novel languages are decidable, acceptable, or undecidable.
  4. Convert a problem to an equivalent formal representation.
  5. Prove that a complex problem is NP-Complete.




Add to Folder (opens a new window)