* Note: In the questions below, the node list should have to form (a, b, c, d, ... ] where "'a'' is the first element of this list that gets taken out for inspection, and the rest are ordered from left to right. That is, Get-First-Node ([a, b, c, d ...]) = a. * Note: Depth is 0 at the root, and increases by 1 as you follow the edge downward. That is, depth equals the number of operator you executed to reach the current level. 1 Uninformed Search BOB 20 22 28 29 3 Figure 1: Search Trees. Consider the search tree in Fig. 1. Assume that the exploration of the children of a particular node proceeds from the left to the right for all search methods in this section. Question 1 (5 pts): Consider depth first search. When the goal is 20 and the node is reached (taken out of node list), (1) what are the nodes that remain in the node list? (list them in the correct order). Also (2) which nodes have been visited until then, in what order? Question 2 (5 pts): Consider breadth first search. When the goal is 12 and the node is reached (taken out of node list), (1) what are the nodes that remain in the node list? (list them in the correct order). Also (2) which nodes have been visited until then, in what order? Question 3 (5 pts): Why is the space complexity of BFS O(6d+1), not Obd), where b is the branching factor and d is the goal depth? Question 4 (5 pts): Can depth limited search become incomplete in the case of the finite search tree above? If so, give an example. If not, explain why not. Question 5 (5 pts): Consider iterative deepening search. When the goal is 21, how many nodes are visited before reaching that node? * Note: In the questions below, the node list should have to form (a, b, c, d, ... ] where "'a'' is the first element of this list that gets taken out for inspection, and the rest are ordered from left to right. That is, Get-First-Node ([a, b, c, d ...]) = a. * Note: Depth is 0 at the root, and increases by 1 as you follow the edge downward. That is, depth equals the number of operator you executed to reach the current level. 1 Uninformed Search BOB 20 22 28 29 3 Figure 1: Search Trees. Consider the search tree in Fig. 1. Assume that the exploration of the children of a particular node proceeds from the left to the right for all search methods in this section. Question 1 (5 pts): Consider depth first search. When the goal is 20 and the node is reached (taken out of node list), (1) what are the nodes that remain in the node list? (list them in the correct order). Also (2) which nodes have been visited until then, in what order? Question 2 (5 pts): Consider breadth first search. When the goal is 12 and the node is reached (taken out of node list), (1) what are the nodes that remain in the node list? (list them in the correct order). Also (2) which nodes have been visited until then, in what order? Question 3 (5 pts): Why is the space complexity of BFS O(6d+1), not Obd), where b is the branching factor and d is the goal depth? Question 4 (5 pts): Can depth limited search become incomplete in the case of the finite search tree above? If so, give an example. If not, explain why not. Question 5 (5 pts): Consider iterative deepening search. When the goal is 21, how many nodes are visited before reaching that node