1. Fill in the following:

S₀ = <box closed, rope tied, rock smooth>

S_Gj = <box open, ?, ?>

Also full credit for S_G = <box open, rope cut, rock broken>

or reasonable variations.

(we did not talk in this class about most general and most specific representations.)

Operators

BreakRock: <?, ?, rock smooth> ® <?, ?, rock broken>

Also full credit for BreakRock: <?, ?, ?> ® <?, ?, rock broken> because we did not say that you can only break the rock once.

CutRope: <?, rope tied, rock broken> ® <?, rope cut, rock broken>

Also full credit for CutRope: <?, ?, rock broken> ® <?, rope cut, rock broken> because we did not say that you can only cut the rope once.

2. The state is not reachable because there is no way to get there from the start state with the operators specified.
3. Table

Writing out the operators is also OK.

Use broken rock to cut tied rope: rock broken, rope tied -> rope cut.

Open box: rope cut, box closed -> box open.

1. Minimax search.
2. Bi-directional breadth-first search
3. Still bi-directional breadth-first. A* requires a function that always underestimates h(S-curr)
4. Depth-limited depth-first search. DFS (alone) OK too.
5. Hill-climbing, because space is unimodal. Half-credit for best-first.

1. Priority queue:

2. h is admissible because it always underestimates the true cost.

i is not because it overestimates, for example at node H, i=2 but cost=1

2. Making a suboptimal move against an opponent who may make mistakes might be better because

• it might trick your opponent into making a mistake -- for example, the "Fool's Mate" in chess
• if you are losing it might give you a chance to capitalize on your opponent's mistakes and win, rather than just be guaranteed a small loss.

(One reason is enough for full credit.)

1. How would you formulate this as a job shop scheduling problem using each document's tasks as variables? ...

2. ... using each machine's status as a variable?

Variables are machine assignments at each time:
Let's say F1 is what machine F is doing at time 1.
Variables would be F1, F2, F3, ... , S1, S2, S3, ... , M1, M2, M3, ... , L1, L2, L3, ...
Values for variables are just the component tasks that need to be done:
D1F, D1S, D1M, ..., Idle
Constraints are identical to those in which the tasks are the variables and jobs are the values.

1. WatchingMovie
2. No, it is not sunny
3. InPittsburgh, RidingBicycle, WatchingMovie
4. It is still consistent. (It just means you won't be in Pittsburgh.)

1. Ø A v B
2. Ø C v Ø D
3. " x:P(x) ® Q(S1(x) ^ R(x, S1(x))
4. " x:S(x) v " y:T(y)

1. Semantic network

2. Exponential

3. Semantic network, redrawn

1. Yes, it parses
2. Not parsable. Add: <Performance> ® skiing
3. Not parsable. Add: <Performance> ® <Performance> and <Performance>
   Also OK is a top-level rule:
   <Compliment ® Your <Performance> and <Performance> was <Superlative.
4. No. You cannot add a rule that prevents the existing grammar from recognizing "Your novel was novel." (With an ATN you might be able to add a constraint that did so.) 1 point for "No" with no explanation.

[ head: clean

agent: kim

object: floor

instrument: mop]

2/5 for conceptual dependency structure

1. Experts don’t always know what they know. Experts may not be able to express what they know they know in rules.
2. Remind the domain expert to think aloud when he or she falls silent -- that's it.
   2 points for saying to speak when expert falls silent but not specifying what to say.
3. Slow down time and run two-phase protocol analysis on slowed-down examples.
4. A system that performs worse than experts could cost much less, or be available more hours or to more people. For example: recommender systems for online shopping.
5. New axioms. Also OK: sets of rules.

1. 5/100 = 1/20 = 0.05
2. P(Winter) = 0.25 + 0.10 = 0.35 = 35/100 = 7/20
3. P(Happy|Fall) = 0.10 / (0.10 + 0.05) = 0.10 / 0.15 = 10/15 = 2/3
4. P(Sad|Summer) = P(Summer|Sad) * P(Sad) / P(Summer)

= (30/55 * 55/100) / 35/100 = 30/35 = 6/7

P(Summer|Sad) = (30/100) / (10/100 + 10/100 + 30/100 + 5/100) = 30/55

P(Sad) = 10/100 + 10/100 + 30/100 + 5/100 = 55/100

P(Summer) = 35/100 = 30/100 + 5/100

5.a. Can not compute P(Sad|Cold) because you lack knowledge of conditional independence.

5.b. P(Happy|Warm) = P(Happy ^ Warm) / P(Warm) [by chain rule]