CSC384H1Y Final Examination AUGUST 2019
Question 1. True/False [10 marks]
Circle either True or False to indicate the truth of each of the following statements. 1 mark each.
No marks will be deducted for incorrect answers.
(a) [1 mark] A* with a heuristic that is not completely admissible may still find the shortest path from the start state to the goal state.
TRUE FALSE
(b) [1 mark] Every Constraint Satisfaction Problem (CSP) with n-ary constraints can be re-written as a CSP with only binary constraints.
TRUE
(c) [1 mark] factor is finite.
TRUE
(d) [1 mark]
TRUE
(e) [1 mark]
up, down, and diagonally). In this context, manhattan distance is an admissible heuristic for the problem of moving the king from square A to square B.
TRUE FALSE
Total Pages = 20
Page 2 cont’d. . .
FALSE
Breadth first search is complete if the state space is infinite but the branching
FALSE
Every CSP with only unary constraints is solvable.
FALSE
On a chess board, the king can move one space in any direction (left, right,
CSC384H1Y (f) [1 mark]
TRUE
Final Examination AUGUST 2019
Uniform-cost search will never expand more nodes than A*-search. FALSE
The minimum remaining value heuristic (MRV) provides a way to select the next
(g) [1 mark]
value to assign a variable in a backtracking search for solving a CSP.
TRUE FALSE
(h) [1 mark] Backtracking search only checks if a constraint has been violated once all variables in the problem are assigned a value.
TRUE FALSE
(i) [1 mark] When using expectimax to compute a policy, re-scaling the values of all the leaf nodes by multiplying them all with 10 can result in a different policy being optimal.
TRUE FALSE
(j) [1 mark] By using the most-constrained variable heuristic and the least-constraining value heuristic we can solve every CSP in time linear in the number of variables.
TRUE FALSE
Total Pages = 20
Page 3 cont’d. . .
CSC384H1Y Final Examination AUGUST 2019
Question 2. CSP: Short Answer [10 marks]
The objective of the Sudoku game that is illustrated above is to place numbers 1, 2, 3, 4 on the 4×4 grid such that each row, column, and 2×2 box contains each number only once. In the illustration, some cells have assigned values; those that do not are labelled with letters (e.g. A1,A2…D3). Assume you are solving this puzzle as a CSP that contains only binary not-equals constraints.
(a) [2 marks] Assume you have been using forward checking and A3 is chosen for assignment. List all values (in any order) that might be selected by the Least Constraining Value (LCV) Heuris- tic.
(b) [3 marks] Assume you have been using forward checking and no variable has been chosen for assignment. List all unassigned variables (in any order) that might be selected by the Minimum Remaining Values (MRV) Heuristic.
(c) [2 marks] Given the current assignments, the cell labelled D3 cannot be a 1 or 2. If we run GAC-enforce on the current CSP, will these values be pruned? (Circle One)
YES
(d) [3 marks]
NO
What does it mean for a CSP to be ”arc consistent”?
Total Pages = 20
Page 4 cont’d. . .
CSC384H1Y Final Examination AUGUST 2019 THIS IS AN EXTRA PAGE FOR ROUGH WORK.
Total Pages = 20 Page 5 cont’d. . .
CSC384H1Y Final Examination AUGUST 2019
Question 3. Bayes Net [16 marks]
(a) [3 marks] For each of these three networks above, write the joint distribution (i.e. P(A,B,C))asaproductofthefactorsthatareimpliedbythenetwork(i.e. P(X,Y)=P(X)P(Y|X)).
(b) [2 marks] Using the joint distribution you wrote down for the network labelled #2, write down a formula for P(A,C).
(c) [4 marks] In the network labelled #1, show that A is independent of C given B.
Total Pages = 20 Page 6 cont’d. . .
CSC384H1Y (d) [4 marks]
Final Examination AUGUST 2019
In the network labelled 3, show that A is independent of C given B.
(e) [3 marks]
entries are contained in the following probability tables and what is the sum of all the values in these tables?
X, Y and Z are Boolean variables (i.e. they can be True or False). How many
Table
Entries
Sum
P(X,Y|Z)
P (X, Y |Z = T rue)
P(X|Y,Z)
Total Pages = 20 Page 7 cont’d. . .
CSC384H1Y Final Examination AUGUST 2019 THIS IS AN EXTRA PAGE FOR ROUGH WORK.
Total Pages = 20 Page 8 cont’d. . .
CSC384H1Y Final Examination AUGUST 2019
Question 4. Bayes Net [15 marks]
In the Bayesian Network above, all variables are Boolean. In the tables below we use upper case to indicate the variable and lower case to indicate the values for a variable.
The conditional probability tables for the network are:
A
a
F
f
B
b
C
c
E
e
D
d
1/2
1/2
a
9/10
a∧b
9/10
c∧f
1/2
c
9/10
-a
3/10
-a ∧ b
2/5
-c ∧ f
1/2
-c
3/10
a ∧ -b
7/10
c ∧ -f
1/10
-a ∧ -b
3/5
-c ∧ -f
3/10
(a) [2 marks] YES
(b) [3 marks] above.
Is this network a polytree? (Circle One) NO
Of the following statements, circle the ones that are asserted by the network
1. P(A,F) = P(A)P(F)
2. P(E|C,A,D) = P(E|C)
3. P(D|F,A,B) = P(D|A,B)
Total Pages = 20 Page 9 cont’d. . .
CSC384H1Y Final Examination AUGUST 2019
(c) [2 marks] Assume you are asked to compute P(D|e). Which elimination ordering results in a larger elimination width? (Circle One)
C,A,B
(d) [8 marks] of fractions.
A,B,C
Calculate P (D| − e). You may leave your answer as sums of products consisting
Total Pages = 20
Page 10 cont’d. . .
CSC384H1Y Final Examination AUGUST 2019 THIS IS AN EXTRA PAGE FOR ROUGH WORK.
Total Pages = 20 Page 11 cont’d. . .
CSC384H1Y Final Examination AUGUST 2019
Question 5. Hidden Markov Models [8 marks]
In the Hidden Markov Model above, state variables Xt are Boolean and emission variables Et are drawn from the domain {1, 2, 3}. The CPTs to specify the model are below.
State
P(X1)
State
P (Xt+1|Xt)
State
Et
P (Et|Xt)
Xt =True
1
1/10
Xt =True
2
3/10
Xt =True
3
3/5
Xt =False
1
3/5
Xt =False
2
3/10
Xt =False
3
1/10
(a) [3 marks] List three conditional independence relationships that exist in this HMM.
Total Pages = 20 Page 12 cont’d. . .
Xt+1
X1 =True
1/2
Xt =True
True
1/4
X1 =False
1/2
Xt =True
F alse
3/4
Xt =False
True
1/5
Xt =False
F alse
4/5
CSC384H1Y Final Examination AUGUST 2019 (b) [5 marks] Calculate P (X3 = T rue|E1 = 1, E2 = 2, E3 = 3). You may leave your answer as
products and/or sums of fractions.
Total Pages = 20 Page 13 cont’d. . .
CSC384H1Y Final Examination AUGUST 2019
Question 6. Logic [18 marks]
(a) [6 marks] Translate the following English sentences into first-order logic using only these
predicates: Dog(x), Lazy(x), Fetches(x, y), Frisbee(x), SleepAllDay(x), Catches(x, y), Healthy(x). 1. No lazy dog will fetch any frisbees.
2. Some dogs can catch frisbees and some can’t.
3. Dogs that sleep all day are either not healthy or lazy or both.
(b) [6 marks] For each of the pairs below, give the most general unifier (MGU) or state why no unifier exists. If a unifier exists, provide the expression that results from the unification. In all of the expressions that follow, the only variables are X, Y , and Z; a, b and c are constants.
1. M(h(a),Y,Y) and M(X,g(X),Z)
2. M(g(c),Y,f(X,Y)) and M(Z,h(Z),f(c,Z))
3. M(g(X, X), h(Z, b), f(Z, X)) and M(Y, h(g(a, a), b), f(Y, a))
Total Pages = 20 Page 14 cont’d. . .
CSC384H1Y Final Examination AUGUST 2019
(c)
• • •
[6 marks] Consider a first-order language L containing the following basic symbols: Constants, a, b, c, d
The binary predicate m and n
The unary predicates p and q
Let M = ⟨D, Φ, Ψ, V ⟩ be a model for L with domain D = {A, B, C, D}, and i Φ(a)=A,Φ(b)=B,Φ(c)=C,Φ(d)=D
ii Φ(m)={(A,B),(C,B),(B,D)} iii Φ(p) = {C, A}
iv Φ(q)={B,D}
Which of the following formulae are satisfied by M. Circle either True or False. 1 mark each. No marks will be deducted for incorrect answers.
• m(a, b) ∨ q(c)
• ∃X.p(X) ∧ q(X)
• ∀X,Y.m(X,Y)∨m(Y,X)
• ∀X.p(X) → ¬∃Y.m(Y, X)
• ∃X,Y¬m(X,Y)→¬p(X)
• ∃X,Y.(p(X)∧q(Y))→m(Y,X)
TRUE TRUE TRUE
TRUE TRUE TRUE
FALSE FALSE FALSE
FALSE FALSE FALSE
Total Pages = 20
Page 15
cont’d. . .
CSC384H1Y Final Examination AUGUST 2019 THIS IS AN EXTRA PAGE FOR ROUGH WORK.
Total Pages = 20 Page 16 cont’d. . .
CSC384H1Y Final Examination AUGUST 2019
Question 7. Resolution [23 marks]
(a) [8 marks]
Given predicates P,Q,R and variables x,y,z; convert the following sentences to clausal form: (Recall that the 8 steps are: eliminate implication, move negation inward, standardize variables, skolemize, convert to prenex, distribute ∧ over ∨, flatten conjunctions and disjunctions, convert to clauses.) Clearly indicate any Skolem functions or constants used in conversion. Note each formula might give rise to more than one clause so number each clause generated.
1. ∀x.R(x)→∃y.P(x,y)
2. ∃x,∀y.(Q(x,y)∧Q(y,x))∨¬R(y)
3. ∀x,∀w.¬P(w,x)→∃z.(R(z)∧Q(x,z))
4. ∃y.R(y)∧∀x.Q(y,x)
Total Pages = 20 Page 17 cont’d. . .
CSC384H1Y Final Examination AUGUST 2019
(b) [15 marks] Consider the following set of clauses, where K, P, L, Q and M are used to denote predicates; h and g are used to denote functions; a, b, and c are constant symbols; and X, Y , and Z are variables. Clauses 1–6 come from a first-order logic knowledge base. Clause 7 contains the negation of the clause you are trying to prove.
Construct a proof of the empty clause by resolution refutation using the notation developed in class. That is, every new clause must be labeled by the resolution step that was used to generate it. For example, a clause labeled R[4c,1d]{x = a,y = f(b)} means that it was generated by resolving literal c (the 3rd literal) of clause 4 against literal d (the 4th literal) of clause 1, using the MGU {x = a,y = f(b)}.
1. K(h(X)),P(g(X))
2. Q(h(Y),g(Y)),¬L(X,g(Y))
3. ¬M(X),¬P(Y),L(c,Y)
4. ¬M(X),L(a,g(X))
5. ¬Q(h(a), X ), K (h(a))
6. M(c)
7. ¬K(h(a))
Total Pages = 20
Page 18
cont’d. . .
CSC384H1Y Final Examination AUGUST 2019 THIS IS AN EXTRA PAGE FOR ROUGH WORK.
Total Pages = 20 Page 19 cont’d. . .
CSC384H1Y Final Examination AUGUST 2019 THIS IS AN EXTRA PAGE FOR ROUGH WORK.
Total Marks = 100
Total Pages = 20 Page 20 End of Examination