ARl711S - FIRSTOPPORTUNITYEXAMINATIONJUNE 2023
QUESTION 3: CSP
[20]
ARl711S Exams is coming up, and the ARl711S staff have yet to moderate the exam in order
to produce the memorandum. There are a total of 6 questions on the exam and each
question will cover a topic. Here is the format of the exam:
• Question 1: Search
• Question 2: Games (Adversarial Search)
• Question 3: CSPs
• Question 4: MDPs
• Question 5: True/False
• Question 6: Short Answer
There are 7 people on the course staff: Stantin, Luciano, Paulina, Judy, Kyle, Michael, and
Nick.
Each of them is responsible to work with Prof Jose Quenum on one question (but a
question could end up having more than one staff member, or potentially zero staff
assigned to it). However, the staff are pretty quirky and want the following constraints to
be satisfied:
(i) Luciano (L) will not work on a question together with Judy (J).
(ii) Kyle (K) must work on either Search, Games or CSPs
(iii) Michael (M) is very odd, so he can only contribute to an odd-numbered
question.
(iv) Nick (N) must work on a question that's before Michael (M)'s question.
(v) Kyle (K) must work on a question that's before Luciano (L)'s question
(vi) Stantin (S) does not like grading exams, so he must work on True/False.
(vii) Judy (J) must work on a question that's after Nick (N)'s question.
(viii) If Stantin (S) is to work with someone, it cannot be with Nick (N).
(ix) Nick (N) cannot work on question 6.
(x) Paulina (P) cannot work on questions 4, 5, or 6
(xi) Luciano (L) cannot work on question 5.
(xii) Luciano (L) must work on a question before Paulina (P)'s question.
3.1 Model this problem as a constraint satisfaction problem (CSP).Variables correspond (4)
to each of the staff members, J, P,N, L, M, S, K, and the domains are the questions
1, 2, 3, 4, 5, 6. After applying the unary constraints, what are the resulting domains
of each variable?
3.2 If we apply the Minimum Remaining Value (MRV) heuristic, which variable should
(2)
be assigned first?
3.3 Realizing this is a tree-structured CSP,we decide not to run backtracking search, and
instead use the efficient two-pass algorithm to solve tree-structured CSPs.We will
run this two-pass algorithm after applying the unary constraints from part 3.1.
Below is the linearized version of the tree-structured CSPgraph for you to work
with.
4