$3.)$ Breadth First Search $($BFS$).$ When expanding, expand from left to right $($i$.$e$.,$ if a child has two

nodes, add the one on the left to the fringe first$).$ Although you will need to use a standard

queue and set $($to keep track of visited states$),$ you do not need to draw them here for

points$/$correctness$,$ but you may want to draw them on scrap paper below to help.

Nodes$/$Paths on Fringe

Iteration

#

Path depth Path depth Path depth Path depth Path depth

$1$ S $0$

$2$

$3$

$4$

$5$

$6$

$7$

$8$

$9$

$10$

$11$

$12$

$13$

$14$

How many nodes were expanded $($i$.$e$.,$ how many iterations did it take? $\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_$

What was the path computed by this search strategy? $\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_$

Was the computed path optimal? $\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_$