ECE 66400 - Formal Languages, Computability, and ParallelizationCredits: 3
Areas of Specialization(s):Computer Engineering
Normally Offered: Fall - odd years
Topics in computability theory and formal languages include recursive function theory, the equivalence of various generic programming languages for numeric calculations and string manipulations, regular languages and finite state automata, and context-free and context-sensitive languages. In complexity theory, emphasis is on the theory of NP-completeness, including proof methods, the distinctions between strong- and weak-sense NP-completeness, NP-hardness, and performance-guaranteed approximation algorithms.
- Computability, Complexity, and Languages, 2nd Edition, Davis and Weyuker, Academic Press, 1994, ISBN No. 012206380-5.
- Computers and Intractability: A Guide to the Theory of NP-Completeness, Garey and Johnson, W. H. Freeman and Company, 1979, ISBN No. 0716710447.
Recommended Text(s): None.
|1||Recursive Function Theory|
|Calculation on Strings|
|2||Deterministic and Non-Deterministic Turing Machines|
|2||Regular Languages and Finite Automata|
|2||Proof Methods for NP Completeness|
|1||Weak and Strong NP-Completeness for Number Problems|