Format
The prelim exam in Theory will include a combined letter grade for the three exams in CS2110.
The threshold for passing the prelim will be an A or better.
The 2110 final and preliminary exam date and time will be posted on the course website maintained by the
current 2110 instructor.
Reading list
Books:
1. Hopcroft and Ullman, Introduction to automata theory, languages and computation.
2. Davis and Weyuker, Computability, Complexity and Languages.
3. Garey and Johnson, Computers and interactability.
Theory of Computation
Automata Theory:
Finite Automata: Deterministic and nondeterministic finite automata, regular expression, closure properties,
pumping lemma, state minimization (Myhill-Nerode Theorem).
Context Free Language: Deterministic and nondeterministic pushdown automata, context free grammars,
their normal forms, pumping lemmas, closure properties and decision algorithms.
Context Sensitive Language: Context sensitive grammar, linear bounded automata, closure properties and
decision algorithms.
Turing Machine Model: Chomsky hierarchy, type-0 grammars, Turing machine model (deterministic and
nondeterministic).
Computability Theory:
Loop programs, primitive recursive functions, partial recursive functions, Godel numbering universal program,
Halting problem, recursive sets, recursively enumerable sets, decidability and undesirability, many to one
reducibility and completeness results, s-m-n theorem, recursion theorem, Rice theorems (both).
Complexity Theory:
Blum's axioms, gap theorem, speedup theorem, basic theorems about abstract complexity measures.
Time and space bounded computation, time and space hierarchy theorems, complexity classes P, NP, Co-NP,
L, NL, polynomial time hierarchy and basic known/unknown results, relativization and oracle computations.
NP-Completeness and Cook's theorem, other NP-complete problems and proofs.
PSPACE-Completeness, log space reducibility and NL-Completeness and NP-hardness.
|
