## CS 381K: Midterm Study Guide

### Topics Covered in Class:

1. State Space Search: definition of State Space; breadth-first, depth-first, bounded depth-first searches: algorithms, comparisons, advantages, disadvantages; iterative deepening; uniform-cost search; heuristic search: functions f, g, h and their meanings; A* algorithm; admissability of A*; IDA*; hill climbing; effect of having extra operators that are not needed for a given problem.
2. Problem Reduction Search: definition; comparison to state space search; AND/OR graph; solution to an AND/OR graph; use of a model to find counter-examples; when to pick node most likely to succeed (fail).
3. Descriptions of games with AND/OR graphs: game tree; reason for using an AND/OR graph; static evaluation function; depth bound; minimax position evaluation; be able to do a minimax evaluation of a given game tree. Alpha/beta search: algorithm, cutoffs, advantages, comparison to plain minimax search; be able to show alpha/beta search on a given game tree.
4. Other search topics:Waltz filtering; constraint satisfaction; genetic algorithms; simulated annealing.
5. GPS (General Problem Solver): how it works; differences; table of connections; means/ends analysis; problems with GPS.
6. Heuristic Dendral: what it does; the state space; how is the state space reduced?
7. Symbolic algebraic manipulation: examples, uses; canonical forms and reasons for using them; representation of formulas in Lisp.
8. Propositional Logic: well-formed formulas (wffs); interpretations; truth/falsity under an interpretation; valid, invalid, consistent, inconsistent, satisfiable, unsatisfiable; decidability of propositional calculus; equivalence of formulas; normal forms; logical consequence; deduction theorem; backward chaining, forward chaining, resolution for propositional calculus.
9. Predicate Calculus: Elements of a well formed formula (definitions); interpretation (definition); evaluation of a formula under an interpretation; decidability of predicate calculus; prenex normal form; Skolemization; clause form; Herbrand universe and Herbrand base; ground instance; Herbrand's Theorem (statement); substitution; applying a substitution to a formula; unification algorithm; resolution for predicate calculus; deduction tree; level-saturation (two-pointer) method; unit preference; set of support; linear resolution; natural deduction, forward chaining, backward chaining; use of predicate calculus for question answering; answer extraction; Horn clauses; use of predicate calculus for state-space problems: situation calculus, representation of operators; STRIPS: components of a STRIPS operator, how operators are chosen. Planning; plan monitoring. Truth maintenance system (TMS).

### Vocabulary

 A* algorithm add list admissible algebraic simplification alpha/beta search AND node AND/OR graph answer extraction answer literal antecedent arc consistent assert atom or atomic formula average branching factor axiom backed-up value backward chaining backward search beam search best-first search bidirectional search blind search Boolean satisfiability (SAT) bound occurrence of variable bounded depth-first box branching factor breadth-first canonical form chronological backtracking clause closed list closed world assumption (CWA) combinatoric explosion complete conjunctive normal form (CNF) consequent consistent constant constraint network constraint propagation constraint satisfaction problem (CSP) credit assignment problem decidable deduction deduction tree delete list dependency-directed backtracking depth bound depth-first diameter difference effective branching factor entail evaluation function expand a node extension false under an interpretation first-order logic fluent forward chaining forward search frame problem free occurrence of variable function game tree genetic algorithm goal state GPS ground instance Herbrand base or atom set Herbrand universe heuristic function heuristic search hierarchical planning hill climbing Horn clause horizon effect IDA* inconsistent instantiate intension interpretation invalid iterative deepening level-saturation method linear resolution literal local maxima logical consequence means/ends analysis minimax model model checking modus ponens most general unifier (MGU) negation as failure non-monotonic logic open list open world assumption operator OR node parent clauses pattern matching plan monitoring ply precondition predicate predicate calculus prefix premise prenex normal form primitive subproblem problem reduction search propositional logic quantifier representation hypothesis resolvent retract rewrite rule satisfiable set of support simulated annealing situation calculus Skolem constant Skolem function Skolemization sound splitting start state state space state variable static evaluation function steepest ascent STRIPS operator subproblem substitution successor operator symbolic manipulation table of connections tautology term true under an interpretation truth maintenance system (TMS) truth table Turing test two-pointer method unification algorithm unifier uniform cost search unit clause unit preference unsatisfiable valid variable Waltz filtering well-formed formula (wff)