### Solutions to Midterm Exam

1a. There are 2^25 possible 5x5 patterns. In the general case, there are 2^(MN) patterns.

1b. There are a number of possibilities, assuming that a unit-cost move consists of changing one square from black to white (or vice versa). Here are a few reasonable h-functions -- note that each of these cannot overestimate the true cost of a path to the solution.

Number of rows (or columns) whose goal number is different from the current number of black squares.

Sum of error-values for each row (where "error-value" is the absolute value of the difference between the goal and the current number of black squares in the row).

Sum of error-values for each column.

Sum of all row- and column-error-values divided by 2.

2a. The value to MAX of the tree is 3.

2b. The leaves that are examined are: 3, 1, 6, 2, and 0. The others are cut off by alpha-beta pruning.

3a.

FORALL(x)
(IF Number (x)
THEN EXISTS(y) Number(y) AND Prime(y) AND Greater(y, x))
3b.

NOT FORALL(x) (IF Number(x) THEN Prime(x))
3c.

FORALL(x, y)
(IF Number(x) AND Number(y)
AND NOT Greater(y, x) AND NOT Greater(x, y)
THEN x = y)
3d.

FORALL(x)
(IF Number(x) AND Prime(x)
THEN EXISTS(y) (Number(y) AND Prime(y)
AND Greater(y, x)
AND Greater(Add(x, x), y)))
4a.

P(B) = P(B|R) * P(R) + P(B|notR) * P(notR)
= 0.4 + 0.2 = 0.6
P(S|R) = P(S|B) * P(B|R) + P(S|notB) * P(notB|R)
= 0.4 +0.02 = 0.42
P(S|notR) = P(S|B) * P(B|notR) + P(S|notB) * P(notB|notR)
= 0.2 + 0.06 = 0.26
P(S) = P(S|B) P(B) + P(S|notB) P(notB)
= 0.3 + 0.04 = 0.34
4b.

P(R|S) = P(S|R) * P(R) / P(S)
= 0.21/0.34 = 0.62
Qualitatively, this is about what you'd expect: Sparky's bad mood suggests that the Rockies probably lost today.