Note:
Some questions seem straightforward or have general text answers that 
     should be clear from R&N, and so haven't been answered. Sorry!

************************************************************
Solutions to Fall 1996 sample final
************************************************************
1. Standard Bayes' Rule problem:

   Use variables G (guilty) and L (lie detected) (real), both true/false.
   We know:	 P(L=t|G=t) = .80,  P(L=f|G=t) = .20
		 P(L=t|G=f) = .05,  P(L=f|G=f) = .95
   Also:	 P(G=t) = .01,	    P(G=f) = .99
   Then:
			P(L=t|G=f)P(G=f)  	  .05 * .99
	 P(G=f|L=t) =   ----------------  =     ---------------- 
			     P(L=t)		     P(L=t)


	 P(L=t) =  P(L=t|G=f)P(G=f) + P(L=t|G=t)P(G=t)
		=  .05 * .99	    + .80 * .01 
		=  .0495 + .008
		=  .0575			     

2, 3. N/A (not responsible for A* algorithm)

4. NAND is a linearly separable function, where the only negative
   member is the point (1, 1, 1, ... 1). It can thus be represented by
   a single-layer perceptron, e.g. one in which all inputs have weight
   -1, and the output has a step activation function with a threshold
   of -n+1. 

5. SAME is the complement of XOR: (0,0) and (1,1) are positive, while
   (0,1) and (1,0) are negative. It is not linearly separable and can't
   be represented by a single-layer perceptron. Proof by simple graph.

6. (Inference)

7. Standard, as in Assignment 2.  It's often easiest to put formulae
   into conjunctive normal form (see steps on p. 281):

(a) ((p => q) => p) => p ===   ~[~(~p OR q) OR p] OR p    (=>)
		         ===   ~[(p AND ~q) OR p] OR p    (DeMorgan's)
			 ===   [~(p AND ~q) AND ~p] OR p  (DeMorgan's)
			 ===   [(~p OR q) AND ~p] OR p    (DeMorgan's)
			 ===   (~p OR q OR p) AND (~p OR p)  (distribution)
			 ===   T AND T  === valid

(b) F => p	     ===   T OR p  ====	 T	==== valid

(c) If validity is not directly apparent, you might find it easier
    to convert to CNF and then check validity:

    [forall x p1(x) OR forall x q1(x)] => forall x (p1(x) OR q1(x))
    eliminate implication
    === [~forall x p1(x) AND ~forall x q1(x)] OR forall x (p1(x) OR q1(x))
    move ~ inwards
    === [exists x ~p1(x) AND exists x ~q1(x)] OR forall x (p1(x) OR q1(x))
    standardize variables apart (rename)
    === [exists x ~p1(x) AND exists y ~q1(y)] OR forall z (p1(z) OR q1(z))
    move quantifiers left
    === exists x exists y forall z [~p1(x) AND ~q1(y)] OR [p1(z) OR q1(z)]
    remove quantifiers (X and Y are Skolem constants)
    === [~p1(X) AND ~q1(Y)] OR [p1(z) OR q1(z)]
    distribute ANDs over ORs and flatten
    === [~p1(X) OR p1(z) OR q1(z)] AND [~q1(Y) OR p1(z) OR q1(z)]
    (This is now in CNF.)
    Now it's easy to see that formula is valid: 
	Either all things (z) satisfy p1 or there is some entity (X)
			that doesn't, and the same is true for q1.

(d) forall x (p1(x) OR q1(x)) => [forall x p1(x) OR forall x q1(x)]
	(not valid)

(e) [exists x p1(x) AND exists x q1(x)] => exists x (p1(x) AND q1(x))
	(not valid)

(f) exists x (p1(x) AND q1(x)) => [exists x p1(x) AND exists x q1(x)]
    === ~[exists x (p1(x) AND q1(x))] OR [exists x p1(x) AND exists x q1(x)]
    === [forall x ~p1(x) OR ~q1(x)] OR [exists x p1(x) AND exists x q1(x)]
    === [forall x ~p1(x) OR ~q1(x)] OR [exists y p1(y) AND exists z q1(z)]
    === forall x exists y exists z [~p1(x) OR ~q1(x)] OR [p1(y) AND q1(z)]
    === [~p1(x) OR ~q1(x)] OR [p1(Y) AND q1(Z)]
    === [~p1(x) OR ~q1(x) OR p1(Y)] AND [~p1(x) OR ~q1(x) OR p1(Y)]
	As in (c), this is clearly valid.

(g) [forall x exists y p3(x,y)] => [exists y forall x p3(x,y)]
	(not valid)

(h) [exists y forall x p3(x,y)] => [forall x exists y p3(x,y)]
    === [~exists y forall x p3(x,y)] OR [forall x exists y p3(x,y)]
    === forall y ~(forall x p3(x,y)) OR [forall x exists y p3(x,y)]
    === forall y exists x ~p3(x,y) OR forall x exists y p3(x,y)
    === forall y exists x ~p3(x,y) OR forall z exists w p3(z,w)
    === forall y exists x forall z exists w [~p3(x,y) OR p3(z,w)]
    === [~p3(F(y),y) OR p3(z,F(z)]
    === valid

8. This is thoroughly explained in 24.4 - using motion, binocular
   streopsis, texture, shading, and contour are all possible methods
   for extracting depth information.

9. (a) Indexical: Meet me here tomorrow.
       ("here" and "tomorrow" refer to contextually determined place and time.)
   (b) Anaphor: He bought the hot dog and ate it immediately.
       ("it" refers to "hot dog")
   (c) Lexical ambiguity: The food was way too hot for her liking.
       ("hot" might mean spicy hot or temperature hot.)

10. Planning
    (a) flexibility, specify only required, important links
    (b) subsequent added actions will be prevented from clobbering some
	necessary link (by removing precondition) and can be dealt with
	(by promotion, demotion)

11. feedback control

12. Question missing, but this is standard alph-beta pruning, as in
    Assignment 6.