;; File: midterm.review.answers
;; Date: 10/25/93
;; Description: answers to sample questions for the midterm

;; In the following, asterisks (*) are used to indicate questions
;; of comparable difficulty to those appearing on the actual exam.
;; In cases, where an asterisk marks a question with many subparts
;; (e.g., a) .. b) .. c) .., etc.) there will never be more than
;; four subparts and commonly only two or three subparts.
;; You can construct a sample exam from the following questions:
;;      Lisp: 1(b,e,f), 2(a,b), 4, 6(a),
;;      Logic: 3(a,c,e), 4(c,d), 5(a,b), 8(a,b,c)
;;      Search: 4, 5
;;      Advanced representation: 1(a), 2(a)

;; Lisp

1. Evaluate the following expressions.  Note that PROGN takes any
number of expressions, evaluates them in order, and returns the
value of the last one.

a) (cons 'a (append (list 1 2) (list 'c 'd)))                   (*)

answer: (A 1 2 C D)

b) (second (first (rest '(1 (2 3) 4))))                         (*)

answer: 3

c) (eq '(a b (c d)) '(a b (c d)))                               (*)

answer: NIL

d) (member '(y) '(x y z))                                       (*)

answer: NIL

e) (member (+ 2 2) '(1 2 3 4))                                  (*)

answer: (4)

f) (second (mapcar #'+ '(3 6 1) '(3 1 9)))                      (*)

answer: 7

g) (member 7 (mapcar #'+ '(3 6 1) '(3 1 9)))                    (*)

answer: (7 10)

h) (first (rest (rest (mapcar #'(lambda (x y) (if (> x y) x y))
                              '(9 2 8 7)
                              '(3 8 1 0)))))
answer: 8

i) (progn (setq x (list 3 (list 1 2)))                          (*)
          (setf (first (rest (first (rest x)))) 4)
          x)

answer: (3 (1 4))

j) (progn (setq x (cons 5
                       (cons (cons 3
                                   (cons 4 nil))
                             nil)))
          x)

answer: (5 (3 4))

k) (progn (setq x (nconc '(5)
                         (cons 3
                               (cons 4
                                     (cons 7 nil)))
                         nil))
          x)

answer: (5 3 4 7)


2. Consider the following Lisp function.

(defun cs141 (list)
  (cs141tas list 0))

(defun cs141tas (this that)
  (cond ((null this) that)
        ((numberp this) (+ this that))
        ((symbolp this) (* 2 that))
        (t (cs141tas (rest this)
                     (cs141tas (first this) that)))))

a) What is the value of (cs141 '(3 f 5))?                       (*)

answer: 11

b) What is the value of (cs141 '(()))                           (*)

answer: 0 

c) What is the value of (cs141 '(0 2f (c f) 6 s 0))

answer:  12

d) What is the value of (cs141 '((9 0 h) 2f (c f) 6 s 0))

answer: 300


3. Consider the following Lisp function. This one is a way too long
for a question on a 1.5 hour exam but it is a good exercise.

(defun misc (f)
  (let ((gee (aux-misc f nil)))
    (append (first gee) (second gee))))
(defun aux-misc (bar tee)
  (cond ((null bar) tee)
        ((numberp (first bar))
         (aux-misc (rest bar)
		   (list (nconc (first tee) (list (first bar)))
			 (second tee))))
        ((symbolp (first bar))
         (aux-misc (rest bar)
		   (list (first tee)
			 (nconc (second tee) (list (first bar))))))
        (t (aux-misc (rest bar) (aux-misc (first bar) tee)))))

a) What is the value of (misc '((1 m) 2 (fuzzy)))?

answer: (1 2 M FUZZY)

b) What is the value of (misc '((e r 5 1  a) 5 (6) d 2 (g 15 7) t 8 9))?

answer: (5 1 5 6 2 15 7 8 9 E R A D G T)


4.(*) Write a recursive lisp function that takes a nested list of symbols
and numbers and returns a list in this form:
(list-of-all-the-numbers-in-the-list list-of-all-the-non-numbers-in-the-list)

answer: 

(defun separate (x)
  (aux-separate x (list nil nil)))
(defun aux-separate (x nums-and-non-nums)
  (cond ((null x) nums-and-non-nums)
        ((numberp x)
	 (list (cons x (first nums-and-non-nums))
	       (second nums-and-non-nums)))
        ((not (listp x)) 
	 (list (first nums-and-non-nums)
	       (cons x (second nums-and-non-nums))))
        (t (aux-separate (rest x) 
			 (aux-separate (first x) nums-and-non-nums)))))

5. Write a recursive lisp function, insert, that inserts a number x
into a list of numbers arranged in ascending order, such that x is
inserted in a place after a number less than or equal to it, and
before a number larger than it.  With the function insert, write a
recursive lisp function, sorting, that sorts a list of numbers into
ascending order.

answer: 

(defun insert (x alist)
  (cond ((null alist) (list x))
        ((> x (first alist)) 
         (cons (first alist) 
               (insert x (rest alist))))
        (t (cons x alist))))
(defun sorting (alist)
  (cond ((null (rest alist)) alist)
        (t (insert (first alist) 
                   (sorting (rest alist))))))

6. Consider the following abstract data type

(defun TREE (name left-child right-child)
  (list name nil left-child right-child))
(defun TREE-NAME (tree) (first tree))
(defun TREE-MARK (tree) (second tree))
(defun TREE-LEFT-CHILD (tree) (third tree))
(defun TREE-RIGHT-CHILD (tree) (fourth tree))
(defun SET-TREE-MARK (tree val) (setf (second tree) val))

a) (*) Write a recursive lisp function that takes a tree and sets the marks of
each tree node with NIL mark to be T.

answer:

(defun reset (tree)
  (cond ((null tree) nil)
	(t (progn (if (null (tree-mark tree))
		      (set-tree-mark tree 't))
		  (reset (tree-left-child tree))
		  (reset (tree-right-child tree))))))

b) (*) Write a recursive lisp function that takes a tree and returns all
of the non-NIL marks in the tree.

answer:

(defun find-non-nil (tree)
  (cond ((null tree) nil)
      (t (let ((the-mark (tree-mark tree)))
           (append (find-non-nil (tree-left-child tree))
                   (if the-mark (list the-mark) nil)
                   (find-non-nil (tree-right-child tree)))))))

;; Logic

1. (*) Represent the following in propositional logic.

a) Either Jason is dumb or brenda is a genius.

answer: dumb-jason v genius-brenda

b) Jennifer has a cold and either Ralph or Max has the flu.

answer:  has-cold-jennifer ^ (has-flu-ralph v has-flu-max)

c) If Fred has the answer, Peter and Jennifer also have the answer.

answer:  has-ans-fred -> (has-ans-peter ^ has-ans-jennifer)

d) Melvin is crazy if he has a ticket and misses the concert.

answer: (has-ticket-melvin ^ misses-concert-melvin) -> crazy-melvin

e) The pastries at the Gate and Josiah's must be terrible
if they are baked at the ratty.

answer: (baked-at-ratty-gate-pastries -> terrible-gate-pastries) ^ 
        (baked-at-ratty-josiahs-pastries -> terrible-josiahs-pastries)

f) If Bill can't find a job, he will be a househusband and Hillary will be
the breadwinner.

answer: no-job-bill -> (househusband-bill ^ breadwinner-hillary)

2. (*) Convert a (relatively simple) formula involving an implication
to conjunctive normal form. Note that a rule of the form p -> (q ^ r)
can be converted to two rules (a conjunction) p -> q and p -> r.

a) (p ^ q) -> r

answer: (~p v ~q v r)

b) r -> (p v q)

answer: (~r v p v q)

c) r -> (p ^ q)

answer: ((~r v p) ^ (~r v q))

3. Label the following formulas as either satisfiable (but not valid),
valid or not satisfiable given the specified set of interpretations.

a) (and (not (or a (or b (not b)))) (or b a))                   (*)
given all possible interpretations (assignments to {a,b})

answer: not satisfiable

b) (and a (not a) b)                                            (*)
given all possible interpretations (assignments to {a,b})

answer: not satisfiable

c) (or a (or b (not b)))                                        (*)
given all possible interpretations (assignments to {a,b})

answer: valid

e) (or (not a) (not b))                                         (*)
interpretations = ((a false) (b false)),
                  ((a true) (b false))

answer: valid

f) (and b (or (and a c) (and (not a) (not c))))
interpretations = ((a true) (b false) (c true)),
                  ((a true) (b true) (c false)),
                  ((a false) (b false) (c true)),
                  ((a true) (b false) (c true))

answer: not satisfiable

g) (and a (or (not b) a))                                       (*)
interpretations = ((a true) (b false)),
                  ((a true) (b true)),
                  ((a false) (b true))

answer: satisfiable but not valid


4. (*) Represent the following in first-order predicate logic.
Use the predicates mushroom(x), purple(x), and poisonous(x).

a) All purple mushrooms are poisonous.

answer: forall x, (mushroom(x) ^ purple(x)) -> poisonous(x)

b) No purple mushroom is poisonous.

answer: forall x, (mushroom(x) ^ purple(x)) -> ~poisonous(x)

c) All mushrooms are either purple or poisonous.

answer: forall x, mushroom(x) -> ((purple(x) v poisonous(x)))

        - an alternative exclusive-or interpretation -

        forall x, mushroom(x) -> 
         ((purple(x) ^ ~poisonous(x)) v (~purple(x) ^ poisonous(x)))

d) All purple mushrooms except one are poisonous.

answer: exists x, (purple(x) ^ mushroom(x) ^ poisonous(x)) ^
          (forall y, (purple(y) ^ mushroom(y) ^ ~(x = y)) -> ~poisonous(y))

e) There are exactly two purple mushrooms.

answer: exists x, y,
          mushroom(x) ^ purple(x) ^ mushroom(y) ^ purple(y) ^ ~(x = y) ^
           (forall z, (mushroom(z) ^ purple(z)) -> ((z = x) v (z = y)))

Use the predicates banana(x), moon(x), inthesky(x), and onanapplepie(x).

f) All bananas on applepies are in the sky.

answer: forall x, (banana(x) ^ onanapplepie(x)) -> inthesky(x)

g) Only one banana in the sky is on an applepie.

answer: exists x, 
          banana(x) ^ inthesky(x) ^ onanapplepie(x) ^
           (forall y, (banana(y) ^ inthesky(y) ^ onanapplepie (y)) -> (x = y))

h) There is only one banana in the sky that is not on an applepie.

answer: exists x, 
          banana(x) ^ inthesky(x) ^ ~onanapplepie(x) ^
           (forall y, (banana(y) ^ inthesky(y)) -> onanapplepie(y))

i) All bananas in the sky are moons.

answer: forall x, (banana(x) ^ inthesky(x)) -> moon(x)

j) There is only one moon in the sky.

answer: exists x,
          moon(x) ^ inthesky(x) ^ 
           (forall y, (moon(y) ^ inthesky(y)) -> (x = y))

k) There is only one moon in the sky, which is on an applepie.

answer: exists x,
          moon(x) ^ inthesky(x) ^ onanapplepie(x) ^
           (forall y, (moon(y) ^ inthesky(y) ^ onanapplepie(x)) -> (x = y))

l) There is a banana in the sky and a moon on an applepie.

answer: exists x, y, 
          banana(x) ^ inthesky(x) ^ moon(y) ^ onanapplepie(y)

m) There are no bananas in the sky.

answer: forall x, banana(x) -> ~inthesky(x)


5. (*) Consider the following axioms and their corresponding
Lisp representation as rules and facts.

p                       (p)
q                       (q)
z                       (z)
p -> r                  (r if p)
(q ^ r) -> s            (s if q r)
(r ^ s) -> x            (x if r s)
(z ^ p) -> y            (y if z p)
(r ^ x ^ y) -> t        (t if r s y)

a) Using the rules of inference, modus ponens and conjunction, prove t or
state that no such proof is possible.

answer:

 1. p           AXIOM
 2. r if p      AXIOM
 3. r           MP 1,2
 4. q           AXIOM
 5. q r         CONJ 3,4
 6. s if q r    AXIOM
 7. s           MP 5,6
 8. z           AXIOM
 9. z p         CONJ 1,8
10. y if z p    AXIOM
11. y           MP 9,10
12. r s y       CONJ 3,7,11
13. t if r s y  AXIOM
14. t           MP 12,13      QED

b) Will goal reduction succeed on the goal (t)?

answer: 

(t)
(r s y)
(p s y)
(s y)
(q r y)
(r y)
(p y)
(y)
(z p)
(p)
()    QED


c) In general, if the axioms are restricted to rules (horn clauses)
and the rules of inference restricted to modus ponens and conjunction,
will goal reduction always succeed on a goal if there is a proof of
the corresponding conjunction?

answer: yes

6. (*) Given the facts and rules below, determine if goal reduction
would succeed with the goals (i) and (d b).

(x)
(e)
(d)
(t)
(s if e x)
(i if s)
(b if a d)

answer: 

(i)
(s)
(e x)
(x)
()    QED

(d b)
(b)
(a d)  gets stuck because "a" cannot be reduced nor proved.

7. (*) Convert the following wffs to an equivalent wff expressed as a
conjunction of formulas of the form forall x1,x2,...,xn, Phi where Phi
is a disjunction of atomic sentences or their negations containing no
quantifiers. Note that a rule of the form p -> (q ^ r) can be
converted to two rules (a conjunction) p -> q and p -> r.

a) forall x,y, (P(x,y) -> (Q(x,y) ^ R(x,y)))

answer: (forall x, y, ~P(x,y) v Q(x,y)) ^
        (forall x, y, ~P(x,y) v R(x,y))

b) forall z, (exists x,y, above(x,z) ^ above(z,y)) -> sandwiched(z)

answer: 
   forall z, x, y, ~above(x,z) v ~above(z,y) v sandwiched(z)

   - here are the steps in the conversion - 

   forall z, ~(exists x,y, ~(above(x,z) ^ above(z,y))) v sandwiched(z) 
   forall z, (forall x,y, ~(above(x,z) ^ above(z,y))) v sandwiched(z) 
   forall z, x, y, ~(above(x,z) ^ above(z,y))) v sandwiched(z)
   forall z, x, y, ~above(x,z) v ~above(z,y) v sandwiched(z)


8. (*) For each of the following pairs of literals, determine if they
unify.  If so, give the most general substitution; if not, give a
brief explanation.  x, y, and z are variable symbols, a and b are
constants, f is a function symbol, and P is a predicate.

a) P(x,y)        P(z,a)

answer: x -> z, y -> a

b) P(f(y),x)     P(z,f(b))

answer: z -> f(y), x -> f(b)

c) P(f(y),x,x)   P(z,z,f(a))

answer: z -> f(y), x -> f(y), y -> b


9. Consider the sentence ``Heads I win; tails you lose.''
Representing this sentence plus associated domain knowledge
in FOPC, we have the following axioms (Me and You are constants,
Win and Lose are predicates of one argument, and Heads and Tails are
predicates of no arguments.

          i. Heads -> Win(Me)
         ii. Tails -> Lose(You)
        iii. ~Heads -> Tails
         iv. Lose(You) -> Win(Me)

a) Convert each of these four wffs to a disjunction of literals.

answer:   i'. ~Heads v Win(Me)
         ii'. ~Tails v Lose(You)
        iii'. Heads v Tails
         iv'. ~Lose(You) v Win(Me)

b) For each of the disjunctions in (a), specify if it is a Horn clause.

answer: all except iii'.

c) Is it possible to prove Win(Me) using resolution and the above
   formulas written as disjunctions of literals.

answer: yes

d) Can you prove Win(Me) using using goal reduction?

answer: no

;; Search

1. Consider your favorite (small) tree-structured search space.
How many steps are required by depth-first and breadth-first search to
find a goal node?

answer: depends on the search space.

2. Consider your favorite (small) search space defined as a graph.
How many steps are required by depth-first and breadth-first search to
find a goal node?

answer: depends on the search space.

3. Consider the following grid

                            + + + + +
                            + + + G +
                            + + + + +
                            S + + + +
                            + + + + +

Assume that you start searching at S, the goal is at G, and that the
next function for all searches generates the next nodes of the node
H in the following order.

                                 1
                               4 H 2
                                 3

except for heuristic search in which children of the same priority
would be given in that order. (e.g., if the priority goes like Fig 1,
then the order that next returns will be like Fig 2:

                4                  1
              2 H 4              4 H 2
                2                  3

             Fig. 1             Fig. 2

What is the number of nodes (inclusive of the goal and the start) that
each of the following apply the goal predicate to before finding the
goal? Recall that on each iteration, all of the search routines apply
the goal predicate to the first element of the list of nodes unless
that list is empty.

a) depth-first search

answer: 11

b) breath-first search

answer: 20

c) best-first search with the Manhattan distance between a node and the goal
as the heuristic.

answer: 6

d) iterative deepening search with the initial depth as 0 and the depth
incremented by 2 each iteration.

answer: 36

4. (*) Consider the grid shown in Fig 3 with starting node S, goal node G,
and obstacles marked by X.

                            3 + + + G
                            2 + + X +
                            1 S + + X
                            0 + + + +
                              0 1 2 3

                              Fig. 3

Suppose that you search this grid using the heuristic function that is
the Manhattan distance mod 3.  The starting node is at the coordinates
(0 1) and the goal is at the coordinates (3 3).  List the coordinates
of nodes in the order in which they are evaluated by the goal testing
function. Your answer should be of the form (0 1) ... (3 3).

answer:   0 1 2 3 4 5 6 7 8 integers
          0 1 2 0 1 2 0 1 2 integers mod 3

   3 + + + G    3 + + + G    3 0 + + G    3 S 2 + G    3   2 + G
   2 1 + X +    2 1 + X +    2 S 0 X +    2   0 X +    2   S X +
   1 S 1 + X    1   1 + X    1   1 0 X    1   1 + X    1   1 + X
   0 0 + + +    0 S 2 + +    0   2 + +    0   2 + +    0   2 + +
     0 1 2 3      0 1 2 3      0 1 2 3      0 1 2 3      0 1 2 3

     (0 1)   ->   (0 0)   ->   (0 2)   ->   (0 3)   ->   (1 2)   ->

   3   2 + G    3   2 + G    3   2 + G    3   S 1 G    3     S G
   2     X +    2     X +    2     X +    2     X +    2     X +
   1   S 0 X    1     S X    1       X    1       X    1       X
   0   2 + +    0   2 1 +    0   2 S +    0   2   +    0   2   +
     0 1 2 3      0 1 2 3      0 1 2 3      0 1 2 3      0 1 2 3

     (1 1)   ->   (2 1)   ->   (2 0)   ->   (1 3)   ->   (2 3)  ->  (3 3)

5. Make sure you understand the tradeoffs involved in using different
blind search methods for different sorts of search spaces.
(*) For example, the exam might include a question that asks what the
best blind search method is for searching a finite, tree-structured
search space with small depth and large branching factor.

answer: depth-first search

;; Advanced Representation

1. (*) Represent the following in the situation calculus.

a) If the dragon is awake and the dragon is in its hoard and
   the knight enters the hoard then the knight is dead.

answer: a causal rule stating the things that do change
        forall s,
          (holds(s,awake(dragon)) ^
           holds(s,location(dragon,hoard))) ->
          holds(result(s,enter(knight,hoard)),dead(knight))

b) The only change that results if the knight enters the dragon's
   hoard when the dragon is awake and in its hoard is that the
   knight is dead (and therefore not alive).

answer: a frame axiom stating the things that do not change
        forall s,f,
          (holds(s,f) ^ ~(f=alive(knight)) ^
           holds(s,awake(dragon)) ^
           holds(s,location(dragon,hoard)))
          holds(result(s,enter(knight,hoard)),f)

2. (*) Consider the following situation calculus axioms,

holds (0, f1)
holds (0, f2)
forall s, holds(s, f1) -> holds(result(s, e3), f3)
forall s, holds(s, f2) -> holds(result(s, e5), f4)
forall s, (holds(s, f3) ^ holds(s, f4)) -> holds(result(s, e4), f5)

a) Add frame axioms so that holds(result(0,e3),f1).

answer: forall s, holds(result(s,e3),f1)

b) Assuming frame axioms as needed, determine s such that holds(s,f5).

answer: s = result(result(result(0,e3),e5),e4)

        where the required frame axioms are as follows

        forall s, holds(result(s,e3),f2)
        forall s, holds(result(s,e5),f3)



