Theory Prelim (CS2110)

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 CS2110 final and preliminary exam date and time will be posted on the course website maintained by the current CS2110 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.

Sample Exams

Theory: 1994