Date: Mon, 02 Dec 1996 16:01:01 GMT Server: NCSA/1.4.2 Content-type: text/html CSE 473 TOPICS FOR FINAL EXAM

CSE 473 Topic List for the Final Exam

Common Lisp: Evaluation of S-expressions involving

  1. CONS, LIST, APPEND, LET, FIRST, REST, +, *, NULL, =,
  2. SETF, APPLY, QUOTE, DEFUN, IF, PROGN, LAMBDA

Production systems and pattern matching

  1. Unordered and ordered production systems
  2. Discrimination nets

Knowledge representation

  1. ISA Hierarchies and Partial Orders
  2. Propositional Calculus Truth tables, rules of inference
  3. Predicate Calculus
  4. Well-formed formulas
  5. Semantics: Interpretations and models
  6. Quantification and representation of unique existence

State-space search

  1. Computing the size of the state space for the painted squares puzzle
  2. Iterative formulation of depth-first search
  3. Breadth-first search, best-first search, uniform-cost search
  4. A* search algorithm, with f'(n) = g'(n) + h'(n)
  5. Genetic search

Logical reasoning

  1. Proofs in the propositional calculus by perfect induction
  2. Resolution in the propositional calculus
  3. Satisfiability, Tautology and Contradiction in the propositional calculus
  4. Predicate calculus literals and clauses
  5. Reduction to clause form
  6. Unification, most general unifiers
  7. Predicate calculus resolution
  8. Satisfiability, tautology and contradiction in the predicate calculus

Probabilistic reasoning

  1. Bayes rule
  2. Odds

Commonsense reasoning

  1. Case-based reasoning approach to problem solving
  2. Distance functions and distance metrics

Planning

  1. Difference between world space and plan space
  2. Iterative-deepening depth-first search

Learning

  1. Learning as improvement as measured by a function of merit, etc.
  2. Concept synthesis in theory formation, example of prime numbers in AM

Natural-language understanding

  1. Levels of NLU from acoustic to pragmatic
  2. Semantic grammar

Vision

  1. Edge detection with the Roberts cross operator
  2. Representing contours with chain codes
  3. Hough transform (how it works and its main formula)
  4. Medial axis transform ("skeleton")
  5. Ramer's algorithm for polygonal approximation
  6. Guzman's method for labelling a line drawing of blocks

Neural networks

  1. Perceptrons
  2. Fundamental training theorem for perceptrons


tanimoto@cs.washington.edu