Q1. [10 pts] Potpourri: Blast from the Past

(a)  Search. Barbie and Ken are in a building of size H × W × L. Each cell of the building mayor may not contain a toy, and

their mission is to collect all of the toys. It is okay for Barbie and Ken to be in the same cell of the building. (i) [2 pts] Propose aminimal state space representation for this problem.

(ii) [2 pts] What is the size of the state space?

(b) [2 pts] CSPs.

Alice is scheduling job interviews. Nine different companies reached out to interview her this coming week, and she is panicked trying to schedule all of them in just five days!  For the nine companies, three are big (B1 , B2 , B3), three are medium (M1 , M2 , M3), and three are small (S1 , S2 , S3). Write down her constraints formally below:

(c) [4 pts] Games.

(i) [2 pts] Fill out the values on the game tree. Which door does the top maximizernode choose? . Door 1  o  Door 2  o  Door 3

(ii) [2 pts] Which terminal nodes are never explored as a consequence of pruning? (Assume that we prune onequality.)

□ A     □ B     □ C     ■ D     □ E     □ F     ■ G     ■ H     □ I     □ J      ■ K     ■ L

o  None of the above

The following CPTs correspond to the Bayes Net above:

Miles is now interested in calculating P(C = +c|T = −t) via sampling. He generates the following random samples (assume the variables were generated from left to right):

(b) [3 pts] Assuming Miles uses prior sampling:

(i) [1 pt] Bubble in the samples that Miles uses to calculate the final probability.

□ 1     ■ 2     ■ 3     ■ 4     ■ 5

(ii) [2 pts] What is the probability he calculates via prior sampling?

(c) [3 pts] Now assuming Miles uses likelihood weighting:

(i) [1 pt] What weight does Miles assign to each sample?

What final probability does he calculate?

(ii) [2 pts] What is the probability he calculates via likelihood weighting?

Q3. [12 pts] HMMs: Head TA Kirby

Q4. [15 pts] Decision Networks: Coin Toss Game

Alice and Bob are participating in a coin toss game. Both playerstoss two fair coins. Bob’s coins are revealed first, after which he must choose to “continue” or “concede”.  If he concedes, Bob loses $2 and the game ends.  If he continues, Alice’s coins are revealed. If Bob’s coin toss resulted in strictly more heads than Alice’s,he wins $10. However, if he has an equal or lesser number of heads than Alice, Bob loses $10. Assume Bob is rational and his utility is the amount of money he wins.

(a) [2 pts] Sketch the decision network for the game, use the following nodes and node types.

Nodes: B represents the number of heads in Bob’s coins; A represents the number of heads in Alice’s coins; C represents Bob’s choice to continue or concede; U represents Bob’sutility.

Node types: An elliptical node represents a chance node; a rectangular node represents an action node; a diamond-shaped node represents utility.

C                   U

B A

(b) [3 pts] For each scenario where Bob gets 0,  1, or 2 heads, what should Bob’s decision be:  to "continue or "concede"? Justify your answer.

(i) [1 pt] If Bob gets 0 heads:

(ii) [1 pt] If Bob gets 1 heads:

(iii) [1 pt] If Bob gets 2 heads:

New node: R represents the revealed coin, either head (R = H) or tail (R = T). S represents Bob’s decision of whether to see one of Alice’s coins.

C U S

B                   A R

(e) [2 pts] Following the previous part, calculate the conditional distribution of A given R and fill in the table:

(f) [3 pts] (Extra Credit!!!!!, do this last) Following the previous two parts, Alice secretly insists that this new rule should not impact her expected gain. What should the value of cbe to meet this condition? Justify your answer.