## NPTEL An Introduction to Artificial Intelligence Week 6 Assignment Answers 2024

1. Select the CORRECT statements –

- We can use Forward Checking to decide which variable we should assign next.
- Tree-structured CSP can be solved in O(n2d) time.
- Local Search is faster than Systematic Search for large values of n in n-Queens Problem.
- The critical ratio is defined as (number of variables) / (number of constraints).

Answer :-For AnswerClick Here

2. The time complexity of AC-3 algorithm and that of solving nearly tree-structured CSPs using cutset conditioning are, respectively, – (c is the size of cutset)

- O(n
^{2}d^{2}), O((n-c).d^{c+2}) - O(n
^{2}d^{2}), O((n-c).d^{c-2}) - O(n
^{2}d^{3}), O((n-c).dc+2) - O(n
^{2}d^{3}), O((n-c).d^{c-2})

**For Questions 3 to 5 –**

Consider the map of AI-Land. We will use the same map for the following 3 questions.

AI-Land is divided into 7 regions. Two regions are said to be neighbors if they share an edge (or a part of an edge – e.g., 2 and 6 are neighbors). We want to color the regions using one of the 3 colors – Green, Yellow, or Purple so that no 2 neighbors have the same color.

Answer :-For AnswerClick Here

3. According to the heuristics discussed in the videos, which region should be colored first? (If there is a tie between regions, choose the region with the least label number)

Answer :-For AnswerClick Here

4. Suppose we assign Green to the region identified in the previous question. Let x be the label number of the region that we should color next. Let y be the number of colors we can assign to it. What is 4x+3y?

Answer :-

5. Consider that we first color Region 1 with Purple and want to color Region 6 next. Which of the following color (s) should we use?

- Purple
- Green
- Yellow
- We can’t use any colour

Answer :-

6. Which of the following is/are true ?

- Arc Consistency can detect all failures
- Tree-structured CSPs can be solved purely by inference
- Arc Consistency helps propagate information between un-assigned variables
- Tree-structured CSPs can be solved in polynomial time

Answer :-For AnswerClick Here

7. Which of the following is/are false for the standard search formulation for solving CSPs? Here, n is the number of variables, and d is the number of values in the domain of each variable. At every step, we branch by assigning a value to some unassigned variable.

- At depth k, each node has d(n-k) children
- All solutions are found at the same depth
- The number of leaves in the tree is dn
- Iterative deepening depth-first search is the best algorithm to perform the search on the resulting formulation

Answer :-

8. Which of the following heuristics/techniques will help speed up back-tracking search in practice?

- Decomposing the original problem into independent sub-problems by finding connected components in the constraint graph and applying backing tracking search independently to each connected component
- Assigning values to variables with the most number of legal values remaining first
- Using arc-consistency to detect failures early
- Picking the least constraining value of the variable chosen for assignment

Answer :-

9. (True/False) Consider the following constraint graph, where nodes represent variables, edges represent constraints between them and the domains of each variable are indicated using the set notation. If we perform arc-consistency on this constraint graph, then we will be able to detect that no solution is possible.

- True
- False

Answer :-

10. Which of the following is true for solving CSPs with hill climbing using the min-conflicts heuristic

- It can solve almost any randomly generated CSP in near constant time and is the most effective when the ratio between the number of constraints to the number of variables is close to the critical ratio
- After selecting a conflicted variable for moving to a neighboring state, we choose the value of the variable that violates the minimum number of constraints
- The objective function we try to minimize is the number of constraints violated
- After selecting a conflicted variable for moving to a neighboring state, we choose the value of the variable that satisfies the most constraints

Answer :-For AnswerClick Here