CMP140 W07: Final Exam Robert Levinson Date: Wednesday, March 21 , 2007, 4-7pm. There are 44 T/F worth 2 points each and 7 Lisp questions worth 8 points each. Thus, 144 points are possible. {True/False: Simply circle the true answers - 2points each} According to the working definitions we have given in class: - All ``rational" agents are intelligent (IQ greater than 80.0). F - All knowledge is information. T The speaker in the ``CYC video" clearly believes that detailed knowledge representation in First Order Logic and automatic theorem proving are obsolete AI tools. F This SAT matrix is satisfiable: T 0** 101 10* *01 *0* **0 One major area of AI research is machine learning. T You can define new functions directly using the Common Lisp function {\em defun}. T Assume l is a list. These two statements are clearly equivalent: (first(rest l)) and (second l)) T - In Common Lisp, (eval '(eval l)) evaluates the list l at least once. T (assume l does not contain ``l", ``snoc" or ``banana") - In Common Lisp, all s-expressions are considered true unless they are T (the empty list) - In Common Lisp, (butlast l) and (rest (esrever l)) always return the same value. F All SAT matrices that contain 5007 variables and no clauses are satisfiable. T All 100x100 tile puzzles are unsolvable. F Depth first search may find an optimal solution faster than breadth first search. T ``Cycle count" (as in the state solvability method) is an admissible heuristic for the 8-puzzle. T A*-monotone is faster on the average than A*-admissible but will not always find a shortest solution path, even if eleven solutions exist. F In playing chess, humans seem to be better long range planners than computers. T People who divide the world into two kinds of substances: ``good" and ``fun" are more likely to be ontologists than epistemologists. T Existential graphs can not represent XOR or majority. F P(x,x,x) unifies with P(a,y,b) where x and y are variables and a and b are constants. F P(f(A),x) unifies with P(x,f(A)) where x is a variables and A is a constant. T A implies (A subsumes C). F A subsumes (C implies A). T ``Propositional logic" and ``boolean algebra" refer to more or less the same thing. T Propositional logic is not fully decidable. F One advantage that resolution has over Existential Graphs is that resolution does not require conversion to clause form. F Depth-first iterative deepening is guaranteed to terminate in a solution, if a solution exists. T It is easier to define ``intensional" intensionally than it is to define ``extensional" extensionally. T It is possible to write a Lisp program that can (given enough resources) find all ``Checkmate positions" in chess!!! T The K in RIKLS stands for ``knowledge representation". T Nearest neighbor learning is ontologically equivalent to the version space algorithm. F Constructing smallest size decision trees is NP-hard even if one uses an information theoretic measure of diversity to guide the attribute choices. T If A subsumes B, D subsumes B. F The danger of ``overfitting" your data is that your model may work perfectly on the training set, but due to noise, not do so well on future data. T The set of all prime integers can be defined extensionally. F Nearest neighbor is incapable of learning how to play perfect chess. F The game-theoretic value of chess and othello have been proven to be the same. F The following two terms unify: P(x,f(x)), P(A,y) where x and y are variables and A is a constant. T A threshold perceptron with learning rate 1.0 is guaranteed to converge as long as the function to be learned is ``linearly separable". T Nearest neighbor learns an ``extensional definition" of the training set. T One advantage perceptrons have over other learning methods is that perceptrons can incorporate first-order-logic heuristics. F One weakness of nearest neighbor is that it requires the user to supply a distance (closeness) function. T Exponential moving averages tend to take more memory to calculate than simple moving averages. F The diversity of a 6-sided die which we know nothing about is log2(6) bits. T A system must either be deterministic or satisfiable. F * Part III: LISP functions: 8 points each Write a Lisp function FLAMBE that takes a list and inserts the list after each of its top-level members. (flambe nil) is nil. Example: (flambe '(1 2 3)) should return: (1 (1 2 3) 2 (1 2 3) 3 (1 2 3)) (defun flambe (l) (mapcan #'(lambda (x) (list x l)) l)) Write a Lisp function FLATTEN L that simply lists all atoms occurring at any level of a list L in order. Example: (flatten '(1 (2) ((3) 5) (4) 2 (6))) should return: (1 2 3 5 4 2 6) (defun flatten (l) (mapcan #'(lambda (x) (if (atom x) (list x) (flatten x))) l)) Suppose your installation does not come with append or nconc Write a Lisp function (defun myappend (l1 l2) that takes two lists l1 and l2 and returns what append would. example: (append '(1 2 3) '(4 5 6)) = '(1 2 3 4 5 6) (defun myappend (l1 l2) (if (null l2) l2 (cons (first l1) (myappend (rest l1) l2)))) Suppose your installation does not come with AND, write a function (defun myand (l) that takes a list of 1 or more S-expressions and returns NIL if any are NIL, else returns the value of the last expression. Example: (myand '(1 nil 3))) --> nil (myand '(1 2 3)) ---> 3 (defun myand (l) (if (not (member nil l)) (first (last l)))) Write a Lisp function (defun maxbit (l) that accepts a list of bits (1 or 0) as arguments, uses no local variables and returns 1 or 0 for which bit occurs more frequently or nil for neither. You may also not use help functions or ``count" or ``remove" or ``member" or ``length". HINT: What can you do if the first two elements of l are different? HINT2: It is OK to cons a new symbol into the list. example: (maxbit 1 0) --> nil (maxbit (0 1 1)) ---> 1 (maxbit (0 1 1 0 0 1 0 0)) ---> 0 Suppose your installation does not come with Satisfiability Write a Lisp function (defun sat (l) that takes a sat matrix (as lists) and returns t if satisfiable or nil if not satisfiable. You may use help functions. ex: (sat nil) should be nil (sat '((1) (0)) ) should be nil. (sat '((1 * *) (* * 0) (* 1 1)) ) should be t. (defun sat (lofc) (if (null lofc) t (if (null (first lofc)) nil (or (sat (hit lofc '0)) (sat (hit lofc '1)))))) (defun hit (lofc x) (if lofc (if (equal (first (first lofc)) x) (hit (rest lofc) x) (cons (rest (first lofc)) (hit (rest lofc) x))))) Write a Lisp routine (DEFUN FINDPAL (l) that takes a list l and returns a largest top-level sublist S of l that is a palindrome (i.e. S = (reverse S)). The sublist need not be contiguous in l, but must retain the same order. For example, (findpal '(a b d e b c a )) is (a b d b a) or (a b e b a). (defun ispal (l) (equal l (reverse l))) (defun findpal (l) (cond ((ispal l) l) ((equal (first l) (first (last l))) (cons (first l) (append (findpal (rest (butlast l))) (last l)))) ((> (length (findpal (butlast l))) (length (findpal (rest l)))) (findpal (butlast l))) (t (findpal (rest l)))))