For each of the following search methods show the search tree(s) at the time the search terminates:

1. Breadth-first Search
2. Depth-first Search
3. Iterative Deepening Search
4. Uniform Cost Search

Notes: In each case, you should annotate each tree node with a number in parentheses indicating the order in which the node have been expanded. The iterative deepening search method may successively generate several trees; show all of them. Assume that breadth-first, depth-first, and iterative-deepening search terminate when they generate a goal node (i.e., the goal test is performed when a node is generated, not when it is expanded). When everything else is equal, expand the nodes in alphabetical order (e.g., A before C, etc).
 

State	S	A	C	D	F	G	H
h	10	5	4	3	4	0	2

Note: Recall that given a node n representing a state in the graph, the heuristic function h(n) is an estimate of the cost of getting from n to the goal node.

1. Is this heuristic admissible? Why?

2. Show the search trees generated for this problem using the following strategies
   • Greedy Best-First Search
   • A* Search
   In each case, give the value of the evaluation function for each node, and indicate the order in which nodes are expanded. You may assume repeated-state checking. When everything else is equal, expand the nodes in alphabetical order.
    

There are two black tiles (marked with B), two white tiles (marked with W), and a blank space. The goal of the puzzle is to have all the white tiles to the left of all the black tiles (without regard to the position of the blank space). There are two possible moves:

• a tile may move into an adjacent empty cell with unit cost; and
• a tile may hop over one or two tiles into an empty cell with the cost equal to the number of tiles hopped over.

1. Perform the A* algorithm on this problem using as your heuristic function h₁ = "the number of white tiles that are to the right of at least one black tile". Give the search tree after the execution of A* with each node labeled by its f(n) value. Show only nodes generated during the A* search. Also, label each edge between the nodes by the cost of the move. You may assume repeated state checking.

2. Can you propose a more informed, but still admissible heuristic? Prove (give a reasonably formal argument) that your heuristic is more informed than h₁, and that it is admissible.
    

1. Is this sentence satisfiable? If so, how many models does it have?
2. Is the sentence A entailed by S (i.e., does it logically follow from S)?

  KB1:  (A \/ C) => B
  KB2:  C \/ D
  KB3:  D => A
  KB4:  C

Using the above knowledge base and inference rules for propositional logic, derive (i.e. give a proof of) the sentence A /\ B. For each step indicate the rule applied and the sentences used to derive the new sentence.