Answers to the CSE473 midterm. You should have the midterm on hand
when you read through these!

1. a) Breadth first runs across the graph: A B C D E F G H I J K
   b) Iterative deepening is depth first to depth one, then depth two,
      and finally depth three: A A B C D A B E F G L H I J D K
   c) Best first clunks about on the left side with the good heuristic
      values (always taking best available heuristic regardless of
      depth): A B F E G C I J H D K
   d) Beam gets stuck on the left and loses the (correct) right side
      branches: A B E F G (terminate no solution)

2. A. T is satisfiable with the model:
	constants = {albert, sam, ben}
	I(Albert) = albert
	I(Ben) = ben
	I(Student) = {albert, sam}
	I(Studentof) = {<albert, ben>, <ben, sam>}
	I(Prof) = {ben}

      Note that Studentof(x,y) does _not_ imply Student(y)

   B. a) No (could be some other student for Adam to prof over)
      b) No (then again, Boris could be the one for Adam)
      c) No change (just makes Adam the only prof.. could still be other
                    students)
      d) Now, T2 |= Studentof(Adam, Boris) because the only
         (possible) student is Boris. For every other person,
         !Student(person).

   C. Introduce Skolem function c(x) for the exists z with parameter x
      Then, the KB looks like:

1	Student(x1) v Prof(x1)
2	!Prof(x2) v !Student(x2)
3	!Prof(x3) v Student(c(x3))
4	!Prof(x4) v Studentof(x4, c(x4))
	---------------------------------
5	!Studentof(Carl, x5)     New Fact
	---------------------------------
6    !Student(Carl)           Disputed fact
     ---------------------------------
7    Prof(Carl)               Resolve 6 against 1 with x1 = Carl
8    Studentof(Carl, c(Carl)) Resolve 7 against 4 with x4 = Carl
9    {}                       Resolve 8 against 5 with x5 = c(Carl)

3. A. P(C|T) = P(C|M)P(M|T) + P(C|!M)P(!M|T)
      P(M|T) = P(M|S,T)P(S) + P(M|!S,T)P(!S) = 0.85
      P(!M|T) = P(!M|S,T)P(S) + P(!M|!S,T)P(!S) = 1 - P(M|T) = 0.15
      P(C|T) = 0.87
   B. P(C|!S) = P(C|M)P(M|!S) + P(C|!M)P(!M|!S)
      P(M|!S) = P(M|!S,T)P(T) + P(M|!S,!T)P(!T) = 0.765
      P(!M|!S) = 1 - P(M|!S) = 0.235
      P(C|!S) = 0.853
   C. I know (some) Hebrew but have not taken CSE444, so..
      E(winnings) = Prize * P(W|S,!T). For risk neutral, E(winnings) = cost
      P(W|S,!T) = P(W|M)P(M|S,!T) + P(W|!M)P(!M|S,!T)
      P(M|S,!T) = 0.80
      P(!M|S,!T) = 1 - P(M|S,!T) = 0.20
      P(W|S,!T) = 0.046
      cost = Prize * P(W|S,!T)  ==> Prize = cost / P(W|S,!T) ~= $653