Given the following state tree: State (0) expands to (1) \& (2), state (1) to (3) \& (4), and state (2) to (5) \& (6). And the Breadth First Search (BFS) and Depth First Search (DFS) implementation are such that the fringe would look like {(1), (2)\} after expanding (0). Note the fringe is an ordered list* If a search problem starts at state (0), after expanding the first (and only) search node, the fringe looks like {(1),(2)}, implying that (1) will be the next search state expanded. (i) For BFS, what would the fringe look like after expanding state (1)? (1 mark) (ii) For DFS, what would the fringe look like after expanding state (1)? (1 mark) (b) The graph below represents a problem space. Nodes are labelled with a letter and the value of a heuristic function h for the node. Edges are labelled with the cost of traversing the edge. Suppose we want to use the A algorithm on the graph to find the path from node S to node G. (i) Simulate running the A atgorithm on the graph by filling in lines in the table below, showing the f,g, and h values of each node on the queue. We have done the first two lines as an example. If you find a new path to a node already on the queue, update its cost (using the lower f value) instead of adding another copy of that node to the queue. Keep the queue sorted. (6 marks) (ii) For the solution found by A, give the cost and sequence of nodes comprising the path. (2 marks)