CECS 451
Assignment 10
Total: 22 Points
General Instruction
• I recommend you can write your answer using LATEX.
• Submit uncompressed file(s) in the Dropbox folder via BeachBoard (Not email or in
class).
1. Consider the 101 × 3 world shown in Figure 1. In the start state the agent has a choice
of two deterministic actions, Up or Down, but in the other states the agent has one
deterministic action, Right. Assuming a discounted reward function.
(a) (4 points) Compute the utility of each action as a function of γ.
(b) (4 points) Draw the utility of each action for the range 0 ≤ γ ≤ 1 using Matlab of
your familiar numerical analysis software.
(c) (2 points) For γ =
1
2
, which action is recommend? Why?
Figure 1: 101 × 3 world
2. Consider the following data set comprised of three binary input attributes (A1, A2, and
A3) and one binary output:
(a) (2 points) Compute Gain(A1).
(b) (2 points) Compute Gain(A2).
(c) (2 points) Compute Gain(A3).
Figure 2: Example data set
3. (6 points) Consider the XOR function of three binary input attributes (A1, A2, and A3),
which produces the value 1 if and only if an odd number of the three input attributes
has value 1. Draw a minimal-sized decision tree for the three-input XOR function.
