|
Aug 31, 2024
|
|
|
|
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.
Possible Instructional Methods: On-ground. Grading: A-F grading only. Student Learning Outcomes - Upon successful completion of this course students will be able to: - Construct formal models of computation such as DFAs, CFGs, and Turing machines to describe various languages.
- Develop complex proofs to statements regarding the complexity of languages.
- Determine whether novel languages are decidable, acceptable, or undecidable.
- Convert a problem to an equivalent formal representation.
- Prove that a complex problem is NP-Complete.
Add to Folder (opens a new window)
|
|