NOTE: You should work individually for the following homework assignment. Please upload

a pdf and a python file $(.$py$)$ with your answers to the MOODLE.

$[15$ points$]$ Compute the order in which states of the above graph are expanded and the

returned path for each of these graph search algorithms: i$)$ Depth$-$first search; ii$)$ Breadth$-$

first search; iii$)$ Uniform cost search; iv$)$ Greedy best first search using the heuristic $h$

shown on the graph; and v$)A^{*}$ search using the same heuristic. Is the heuristic $)$

admissible? Explain why or why not.

I$)$ DFS path is: $SNPQG$

II$)$ BFS path is: $SQG$

III$)$ UCS path is: $SNPG$

IV$)$ Greedy$\_$path is: $SQG$

V$)?$

VI$)?$