$2$ Depth$-$First Search $($DFS$)$

Consider the same graph as in Question $1.$ This time, perform Depth$-$First Search $($DFS$)$ starting from

node A$.$ Show the order in which the nodes are visited. You can assume that ties are broken alphabetically.

$3$ A$*$ Search

Consider the the graph from Question $1,$ where you are tasked with finding the shortest path from node

$A($the start node$)$ to node $O($the goal node$).$ The graph has uniform edge costs of $1$ for all edges. The

heuristic values $h(n)$ for each node are provided in the table below: $3\mathrm{.}1$ Admissibility of the Heuristic

Based on the heuristic values given above, is the heuristic $h(n)$ admissible for this graph? Justify your

answer by checking whether the heuristic satisfies the admissibility condition for at all nodes in the graph.

$3\mathrm{.}2$ A$*$ search

Irrespective of your answer to $3\mathrm{.}1,$ assume that the heuristic is admissible. Apply the A$*$ search algorithm

to find the shortest path from node $A$ to node $O.$ Show the steps of the algorithm, including: $1.$ The

nodes expanded at each step. $2.$ The total cost $f(n)=g(n)+h(n)$ at each step for each expanded node.

The final path and its total cost.Instructions

Answer the following questions about search algorithms. Show all your work and explain your reasoning

in detail where necessary. Submit your solutions by the due date.

$1$ Breadth$-$First Search $($BFS$)$

Given the following graph, apply the Breadth$-$First Search $($BFS$)$ algorithm starting from node A$.$ Show

the order in which the nodes are visited. You can assume that ties are broken alphabetically.