Consider the problem of finding the shortest path from a to z in the following directed graph: Start at node a and use z as the goal node. Expand neighbours of a node in alphabetical order, and break ties in alphabetical order as well. For example, suppose you are running an algorithm that does not consider costs, and you expand a; you will add the paths to the frontier in such a way that is expanded before . For the algorithms in questions 1.1-1.4, answer the following questions: (a) What nodes are expanded by the algorithm? Order the nodes from first expanded to the last. (b) What path is returned by the algorithm? (c) What is the cost of this path? 1.1. Depth-first search 1.2. Breadth-first search 1.3. A* (use the uninformative but valid heuristic h(x) = 0 for all nodes) 1.4. Branch-and-bound (use h (x) = 0 for all nodes) 1.5. (a) Given your solutions in the previous questions, did BFS and Branch and Bound find the optimal solution? (b) Are BFS and Branch and Bound optimal in general? Explain your answer. (c) Did B&B expand fewer nodes than A*? Explain if your answer is true in general for these two algorithms and why. Consider the problem of finding the shortest path from a to z in the following directed graph: Start at node a and use z as the goal node. Expand neighbours of a node in alphabetical order, and break ties in alphabetical order as well. For example, suppose you are running an algorithm that does not consider costs, and you expand a; you will add the paths to the frontier in such a way that is expanded before . For the algorithms in questions 1.1-1.4, answer the following questions: (a) What nodes are expanded by the algorithm? Order the nodes from first expanded to the last. (b) What path is returned by the algorithm? (c) What is the cost of this path? 1.1. Depth-first search 1.2. Breadth-first search 1.3. A* (use the uninformative but valid heuristic h(x) = 0 for all nodes) 1.4. Branch-and-bound (use h (x) = 0 for all nodes) 1.5. (a) Given your solutions in the previous questions, did BFS and Branch and Bound find the optimal solution? (b) Are BFS and Branch and Bound optimal in general? Explain your answer. (c) Did B&B expand fewer nodes than A*? Explain if your answer is true in general for these two algorithms and why