ECE 66400 - Formal Languages, Computability, and Parallelization

Credits: 3

Areas of Specialization(s):

Computer Engineering

Counts as:

Normally Offered: Fall - odd years

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):
  1. Computability, Complexity, and Languages, 2nd Edition, Davis and Weyuker, Academic Press, 1994, ISBN No. 012206380-5.
  2. 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