ECE 66400 - Formal Languages, Computability, and Parallelization
Course Details
Credits: 3
Areas of Specialization:
- Computer Engineering
Counts as:
Normally Offered:
Fall - odd years
Campus/Online:
On-campus only
Catalog Description:
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.
Required Text(s):
- 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.
Lecture Outline:
| Weeks | Topic |
|---|---|
| 1 | Recursive Function Theory |
| Calculation on Strings | |
| 2 | Deterministic and Non-Deterministic Turing Machines |
| 2 | Regular Languages and Finite Automata |
| 2 | Context-Free Languages |
| 2 | Context-Sensitive Languages |
| 2 | Proof Methods for NP Completeness |
| 1 | Weak and Strong NP-Completeness for Number Problems |
| 1 | NP-Hardness |
Assessment Method:
none