# 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