Part 1 of Problems: Consider a state space where the start state is number 1 and the successor function for state n returns two state, numbers 2n and 2n + 1

a.Draw the portion of the state space for states 1 to 15.

b.Suppose the goal state is 11.List the order in which nodes will be visited for breadth-first search, depth-limited search with limit 3, and iterative deepening search.

c.Would bidirectional search be appropriate for this problem? If so, describe in detail how it would work.

d.What is the branching factor in each direction of the bidirectional search?

Part 2 of Problems:

Prove each of the following statements:

a.Breadth first search is a special case of uniform-cost search.

b.Breadth first search, depth-first search, and uniform-cost search are special cases of best first search.

c.Uniform-cost search is a special case of A* search.