An Introduction to Artificial Intelligence Week 6
Course Name: An Introduction to Artificial Intelligence
Course Link: Click Here
These are An Introduction to Artificial Intelligence Answers Week 6
Q1. Which of the following is true in the context of the standard search formulation of CSPs?
(there are n variables, each of which can take d values, at every step you branch by assigning a value to some unassigned variable)
a. All solutions appear at the same depth in the search tree
b. There are dn leaf nodes in the search tree, one for each possible assignment of values to the variables
c. There are n!dn leaf nodes in the search tree, n! for each possible assignment of values to the variables
d. Iterative deepening depth first search is the best algorithm to perform the search on the resulting formulation
Answer: a, c
These are An Introduction to Artificial Intelligence Answers Week 6
Q2. What is the worst-case time complexity of solving a CSP containing nk variables, each of which can take d values, if it is known that the problem can be decomposed into k independent subproblems, each containing n variables?
a. O(dnk2)
b. O(dnk)
c. O(kdn)
d. O((d/k)n)
Answer: c. O(kdn)
These are An Introduction to Artificial Intelligence Answers Week 6
Q3. Which of the following methods are unlikely to increase the speed of backtracking search for solving a CSP?
a. Cutset conditioning on a complete (fully connected) CSP graph.
b. Selecting variable with fewest legal values remaining
c. Using arc consistency to detect failures early
d. Selecting the most constraining value for a variable
Answer: a, c
These are An Introduction to Artificial Intelligence Answers Week 6
Q4. In which of the following settings is hill-climbing using min-conflicts heuristic likely to struggle the most?
a. Low number of constraints, low number of variables
b. Number of constraints >> Number of variables
c. Number of constraints << Number of variables
d. Near the critical ratio between number of constraints and number of variables
Answer: d. Near the critical ratio between number of constraints and number of variables
These are An Introduction to Artificial Intelligence Answers Week 6
Q5. Which of the following is true about arc consistency as a method to improve backtracking search based constraint satisfaction algorithms?
a. It helps in detecting failures early by leveraging constraints involving unassigned variables.
b. Arc consistency updates the domain of unassigned variables given the current assignment and detects failure when all the modified domains are empty
c. Arc-consistency can be performed in polynomial time.
d. Backtracking search with arc consistency and forward checking solves CSPs in polynomial time
Answer: a, c
These are An Introduction to Artificial Intelligence Answers Week 6
Q6. Consider the constraint graph given below. Each node can take values from the set {‘a’, ‘b’, ‘c’} and the constraints are that the variables connected by an edge in the constraint graph need to have different values. We will use the following CSP solving heuristics over backtracking searching with forward checking to find a satisfying assignment for the constraints.
I. For selecting which node to assign, select the numerically smallest unassigned node.
II. For assigning value to the node, select the smallest value possible in the current domain(as determined by the forward checking algorithm).
Determine the sequence of nodes that are assigned/re-assigned one by one till a satisfiable solution is reached.
Answer: 0123345
These are An Introduction to Artificial Intelligence Answers Week 6
Q7. In the above problem, suppose that for assigning value to the node, instead of II, the Least Constraining Value Heuristic is used with ties broken in the alphabetical order.
Suppose that nodes x1 ,x2 ,… xk are assigned/re-assigned values v1 ,v2 ,… vk . Determine x1v1x2v2 … xkvk . For example, if the nodes 0,3,1,2,4,5 are assigned a, b, c, a, b, b respectively, the correct response will be 0a3b1c2a4b5b.
Answer: 0a1b2c3b4a5b
These are An Introduction to Artificial Intelligence Answers Week 6
Q8. In the above problem, the following additional unary constraints are added:
Value(0) = a
Value(1) = b
Value(2) = c
Suppose we enforce these constraints(assign 0,1 and 2 with corresponding values) and perform the arc-consistency algorithm AC-3, which of the following are correct about the modified domains of the unassigned variables?
a. Modified domain of variable 3, is {b}
b. Using the modified domains, the search terminates without ever backtracking, i.e without ever re-assigning any previously assigned variable with another value.
c. Modified domain of variable 3 is {a,b}
d. Using forward checking instead of AC-3 would have resulted in the same modified domains for this problem.
Answer: a, b
Q9. For the constraint graph of problem 6, suppose we want to use cycle cutsets to modify it into a tree-shaped constraint graph. How many minimum nodes need to be removed in the process?
Answer: 2
These are An Introduction to Artificial Intelligence Answers Week 6
Q10. Consider constraint satisfaction problems with n variables and a domain of size d. Which of the following are correct regarding the worst case time complexity of algorithms for constraint satisfaction problems?
a. Using the minimum remaining values heuristic and the least constraining value heuristic reduces the worst case time complexity to polynomial in n and d.
b. Worst time complexity is O(nd) irrespective of heuristic.
c. If the minimum cycle cutset has size c, time complexity is O(ndc+2)
d. For a tree shaped constraint graph, time complexity is O(d)
Answer: c. If the minimum cycle cutset has size c, time complexity is O(ndc+2)
These are An Introduction to Artificial Intelligence Answers Week 6
These are An Introduction to Artificial Intelligence Answers Week 6
More Solutions of An Introduction to Artificial Intelligence: Click Here
More NPTEL Solutions: https://progiez.com/nptel/
This content is uploaded for study, general information, and reference purpose only.