Theoretical Computer Science Final Exam Review

Material Covered in Final Exam
Material Covered in Exam #1

Material Covered in Exam #2

Turing Machines
   Computing functions with Turing Machines
   Extensions of Turing Machines:  multiple tracks (show polynomial-time
      transformation to single track), two-way infinite tape (show
      polynomial-time transformation to one-way infinite tape), multiple tapes,
      nondeterministic Turing Machine, multidimensional, multihead
   decides, semidecides

Closure Properties of Recursive and Recursively Enumerable Languages
   Recursive languages are closed under complement, union, intersection\item L
      recursive <=> L and L complement are both recursively enumerable

Chomsky Hierarchy

Logic
   valid, satisfiable, unsatisfiable, interpretation
   propositional logic, predicate logic
   atomic formula, term, atomic sentence, literal, connective, quantifier
   truth assignment, truth table, clausal form
   idempotency, commutativity, associativity, absorption, distributivity,
   tautology, unsatisfiability, modus ponens, modus tolens, and introduction,
   or introduction, and elimination, double-negation elimination,
   unit resolution, resolution
   proof using resolution

Complexity Theory
   polynomially bounded Turing Machine
   polynomially decidable language
   search algorithm vs. decision algorithm
   P, NP, NP Complete, EXP, relationships between these sets
   NP Complete problems:  traveling salesman problem, Hamiltonian cycle,
      satisfiability, 3sat, clique, vertex cover, partition, knapsack
   prove a problem is in NP, prove a problem is in NP Complete
   certificate, witness, reduceability

Exam is on Wednesday, December 8