Term Test 2
Started: Dec 4 at 6:03am
Quiz Instructions
Question 1 20 pts
Consider the following 4×4 Sudoku Puzzle. It is a scaled down version of the normal 9X9 Sudoku puzzle.
We will model this puzzle with a CSP containing 16 variables: A1, A2, A3, A4, B1, B2, B3, B4, C1, C2, C3, C4, D1, D2, D3, and D4, where each variable represents the contents of the cell identified by the row and column labels. The figure gives the domain of each variable, e.g., Dom[B1] = {1, 3, 4} and Dom[D4] = {1, 2, 3}.
The CSP has the following 12 constraints, each of which is over 4 variables and each of which is an all-diff constraint:
(a) The four row constraints R1(A1,A2,A3,A4), R2(B1,B2,B3,B4), R3(C1,C2,C3,C4), R4(D1,D2,D3,D4).
(b) The four column constraints C1(A1,B1,C1,D1), C2(A2,B2,C2,D2), C3(A3,B3,C3,D3), C4(A4,B4,C4,D4).
(c) The four subsquare constraints SS1(A1,A2,B1,B2), SS2(A3,A4,B3,B4),
SS3(C1,C2,D1,D2), SS4(C3,C4,D3,D4).
SS3(C1,C2,D1,D2), SS4(C3,C4,D3,D4).
(a) Given the sequence of constraints listed in the table below, you are to perform GAC-enforce on each constraint in the order given. When you enforce GAC on the i-th constraint you should be starting with the variable domains that have already been reduced by the previous GAC-enforce steps.
For each constraint, list the variables that have had their domains updated by enforcing GAC on that constraint, and for each updated variable, list that variable’s current domain. Do not list variables that have not had their domains updated during this step. If this GAC-enforce step does not prune any variable domains enter none in the table. (A blank entry will not be marked as correct).
You use the same style of table to format you answer (note most browsers allow you to copy and paste the table and then you can fill it in).
Constraint
Variables with Updated Domain
SS1(A1,A2,B1,B2)
SS4(C3,C4,D3,D4)
C1(A1,B1,C1,D1)
SS2(A3,A4,B3,B4)
C3(A3,B3,C3,D3)
C4(A4,B4,C4,D4)
R3(D1,D2,D3,D4)
R1(A1,A2,A3,A4)
(b) Is the CSP GAC after this sequence of constraints have been made GAC? (Yes or No)
If not, make the CSP GAC and specify the final variables’ domains in a 4×4 table like the following
A1 = {…}
A2 = {…}
A3 = {…}
A4 = {…}
B1 = {…}
B2 = {…}
B3 = {…}
B4 = {…}
C1 = {…}
C2 = {…}
C3 = {…}
C4 = {…}
C1={…} C2={…} C3={…} C4={…}
D1 = {…}
D2 = {…}
D3 = {…}
D4 = {…}
View keyboard shortcuts
Edit View Insert Format Tools Table
12pt Paragraph
p View keyboard shortcuts Accessibility Checker 0 words
Switch to raw html editor Fullscreen
Question 2 12 pts
Consider a CSP with the variables A, B, C, D and domains
Dom[A] = {1,2,3} Dom[B} = [1,2] Dom[C] = [1,2] Dom[D] = [1,2,3,4]
Answer the following 6 questions. Clearly mark which answer is for which question!
1. Suppose that the CSP has a single all-diff constraint over all four variables, and no other constraints. List the variable domains after the CSP has been made GAC by GAC-Enforce having been run.
2. Suppose that the CSP has only 6 binary non-equal constraints, one for each pair of variables, and no other constraints. List the variable domains after the CSP has been made GAC by GAC-Enforce having been run.
3. Two CSP problems are equivalent if they are over the same set of variables, and have exactly the same set of solutions. Are the two CSPs in 1 and 2 equivalent. (Answer True or False)
4. Considering the algorithms BT (backtracking), FC (forward checking) and GAC (generalized arc-consistency), which of these would be better when solving the first CSP (with a single all-diff constraint). (Answer BT, FC or GAC).
5. Would FC be more effective in solving the first CSP (with the single all-diff) or the second CSP (with the 6 not-equal constraints)? (Answer first or second).
6. Comparing FC and BT for solving the first CSP (with a single all-diff constraint), do you expect FC to be significantly faster, about equal in performance, or significantly slower than BT. (Answer much faster, about equal, or much slower).
View keyboard shortcuts
p View keyboard shortcuts Accessibility Checker 0 words
Switch to raw html editor Fullscreen
Edit View Insert Format Tools Table
12pt Paragraph
Question 3 14 pts
You sometimes have problems with your mobile data connection being slow. Your main use of data is watching videos on your phone. You generally try to connect to a wifi which doesn’t use up your mobile data. But your viewing habits are not affected by whether or not you have access to wifi, so sometimes you watch a lot of videos with your mobile data, and that uses your data. If you use too much data you can exceed your data quota and then your connection becomes slow. But sometimes the network is slow. When the network is slow your friend (who never uses much data) also has a slow connection.
You want to model this situation with a Bayes network using the following variables S — your mobile data connection is currently slow
V — you have watched a lot of videos this month
V — you have watched a lot of videos this month
W — you have used the wi-fi a lot this month
O — you are already over your data quota this month
N — the cellular network is currently having problems and is slow F — your friend’s mobile data connection is currently slow
Consider the following Bayes nets, A, B, C over these variables.
Answer the following questions.
1. Network A is a correct probabilistic model of this scenario
[ Select ]
2. Network B is a correct probabilistic model of this scenario
[ Select ]
3. Network C is a correct probabilistic model of this scenario
[ Select ]
In this scenario which of the probability statements (each representing a statement of conditional independence) is true.
1. P(N|V,W,O) = P(N)
[ Select ]
2. P(S|V,W,N) = P(S|N,V)
3. P(O|F,S,N,V,W) = P(O|V,W)
Which of A, B, or C is the best probabilistic model of this scenario
[ Select ]
[ Select ]
[ Select ]
Question 4 30 pts
Consider the following Bayes Net with specified CPTs. Each of the variables are true/false variables with domain of values = {t,f}
In the Bayes net above we will use variable elimination (VE) to compute P(F|B=t, E=f) eliminating the variables that need to be eliminated in alphabetic order. Answer the following questions
1. For each factor in the sequence of factors that will be computed by VE as each variable is eliminated, give the variable that will be eliminated (following the
above ordering), the scope of the factor that will be computed, and the size of the factor that will be computed (where the size is the total number of entries in the factor). Use a table like the following to give your answer. Put as many rows in the table as will be needed.
Variable Eliminated
Scope of Factor computed by VE
size (number of entries in factor)
2. For each factor you specified above give a table with its values. Give each value rounded to 3 significant digits. Use a table like the following to specify each of the factors and make sure that you give the factors in the same order that they are computed by VE
in this example table, we are specifying a factor over the variables X, Y, Z by giving the values in the table.
3. Specify the final posterior probabilities, i.e., P(F=t|B=t E=f) and P(F=f|B=t, E=f), rounded to 3 significant digits
4. Use relevance reasoning to determine the posterior probabilities P(D=t|B=t, E=f) and P(D=f|D=t, E=f) and give these probabilities.
View keyboard shortcuts
X
Y
Z
F(X,Y,Z)
‘a’
‘a’
0
0.500
p View keyboard shortcuts Accessibility Checker 0 words
Switch to raw html editor Fullscreen
Edit View Insert Format Tools Table
12pt Paragraph
Question 5 10 pts
Consider again the same Bayes Net
and answer the following questions.
1. What is the elimination width of the ordering C, A, B, E, F, D?
2. What is the elimination width of the ordering A, B, E, D, C, F?
3. What is the elimination width of the ordering F, D, E, A, B, C?
4. Breaking ties alphabetically give the ordering that would be computed with the
min-fill heuristic.
View keyboard shortcuts
p View keyboard shortcuts Accessibility Checker 0 words
Switch to raw html editor Fullscreen
Edit View Insert Format Tools Table
12pt Paragraph
Question 6 10 pts
Copy and fill out the second column of the following table. The second column specifies the list of the variables that are independent of the variable A given variables listed in the first column. If no variables are independent of A given the stated variables, then write none in the answer column. (A blank column will be marked as being incorrect)
Set of Given variables
List of all variables that are independent of A given these variables
none
D
F,G
D,I
C,F,G
View keyboard shortcuts
Edit View Insert Format Tools Table
12pt Paragraph
p View keyboard shortcuts Accessibility Checker 0 words
Switch to raw html editor Fullscreen
Saving…
Submit Quiz