$1)[6$ points$]$ Search algorithms:

For each graph search algorithm given below, write all the expanded states and the solution path returned. S and G are the initial and goal states, respectively. In all cases, assume that ties resolve by expanding the first nodes that appear early in the alphabetical order. For example, if there is a tie between G$,$ C$,$ and S$.$ The expansion order would be C$,$ G$,$ and S$.$

a$)$ Breadth$-$first search:

b$)$ Depth$-$first search:

c$)$ Uniform$-$cost search

$2)[2$ points$]$ Briefly explain why a depth$-$first graph search can be incomplete in infinite spaces. Can this be avoided?

$3)[2$ points$]$ Briefly explain why you can ignore explored states in the graph search version of BFS$.$ Argue with an example that for an explored node, there cannot be another optimal path through the same node in future expansions.

$4)[2$ points$]$ Can uniform cost search and breadth$-$first search return similar results? What should be true for this to happen?

$5)[3$ points$]$ A$*$ search: Run A$*$ tree search on the state space graph given below. Write all the expanded states and the solution path returned. S and G are the initial and goal states. In all cases, assume that ties resolve by expanding the first nodes that appear early in the alphabetical order. h$($n$)$ is given for each node. Is the returned solution optimal? If not, explain what went wrong.