Consider the following graph representing the state space and operators of a navigation problem:

S is the start state and G is the goal state.

• When placing expanded child nodes on a queue, assume that the child nodes are placed in alphabetical order (i.e. if node S is expanded the queue will be: A B).

Assume that we never generate child nodes that appear as ancestors of the current node in the search tree

1. What is the order that breadth first search will expand the nodes? S,A,B,D,C,E,G
2. What is the order that depth first search will expand the nodes? S,B,E,F,D,G
3.What is the order that iterative deepening search will expand the nodes?
4. Describe a search space where iterative deepening performs much worse than depth first search.
5. Construct a search tree where it is possible that DFS will use more memory than BFS.
6. Suppose we have a problem space where there is a uniform branching factor b and there is a single goal node at depth m.

What is the minimum number of nodes expanded and the storage needed for BFS and DFS? (Hint: this question asks about the best case performance of BFS and DFS).