Important: When we use the phrase 'define'. we are looking for a formal definition using some form of formal notation, and not simply an English description or definition. For example: 'Define the initial state for an agent would implies that you explain the action in available for the agent

Each Question Carries equal Marks

Question $1$: $30$ Marks

$(1\mathrm{.}1)$ Highlight the differences between a tree and graph search.

$(1\mathrm{.}2)$ How does a Breadth First Search $($BFS$)$ differ from the general tree search algorithm? What is the major reason for implementing the algorithm in this way? Provide an example to aid your discussion.

$(1\mathrm{.}3)$ Consider an example of a sliding$-$block puzzle game state provided below $($Figure $1).$ Howmany distinct states are there for puzzles of this sort? How many search nodes? Explain how you reached your answer.

$\backslash$table$[[$I$,$N$,$L$,$D$],[$E$,$C$,,$K$],[$B$,$H$,$J$,$O$],[$A$,$F$,$G$,$M$]]$

Figure $1$: Sliding$-$block puzzle