This section of the Midterm exam is open-book, open-notes, approximately one hour in length, with six questions. This follows the earlier separate closed-book, closed-notes section, also about one hour in length.

**Question 1:**
Depth-first search including path lengths: In the figure below, draw the search tree for enough of a depth-first search that the goal 'I' is reached by two distinct paths, starting at node 'A'. In constructing your search tree never include any nodes that are identical to a previous nodes in that path, "no loops" - ABEF... is OK, but ABEB... is not.

Next to each node in your drawing of the search tree place the total path length to that node reached so far by that path. When you are done, state what the path lengths are that you found from 'A' to the goal node 'I'.

To make your search systematic, whenever your node expands to more than one additional one, visit those nodes in alphabetical order, e.g., From 'E', you might choose 'D', 'F', and 'H', in that order (assuming none of the three violated the loop constraint).

You will also find it useful to make copies of the lattice (omitting the node labels for simplicity) and then draw arrows along the paths you found.

**Question 2:**
Resolution proof for propositional logic: Given the following statements and the conclusion to prove, do the standard conversion to conjunctive normal form and carry through a resolution proof.

- Sunny or warm implies no ice: Sun ∨ Warm ⇒ ¬Ice
- No ice implies OK driving: ¬Ice ⇒ OK
- It is sunny: Sun
- The conclusion to be proved - there is OK driving: OK

Notation for the five variables: By examining the diagram, draw at least two diagrams with assignments that satisfy the constraints. For your convenience, here is the alphabet: abcdefghijklmnopqrstuvwxyz EXTRA CREDIT 10 points - SEARCH AND ARC-CONSISTENCY (Sec. 5.2 of AIMA): Repeatedly apply arc-consistency to the constraints to reduce the domains as much as possible. When that is complete, do a depth-first search to find one solution. Search the variables in the order UL, UR, MD, LL, and LR. For each variable, search the domain values in alphabetical order. Some branches of the search may fail, but continuing the search will eventually find a solution, since the problem does have a solution - more than one, actually. |

**Question 4:** Checking validity by using equivalences:
You are to prove that the statement below is valid by applying a series
of equivalences until you reach the value *True*. Since your result
is independent of the values of the three variables involved, you will
have proved that the statement is valid.

(P ⇒ Q) ⇒ ((P ∧ R) ⇒ Q)

**Question 5:** Horn database and AND-OR graphs:
Given the clauses below, prove S by drawing an
AND-OR graph corresponding to the premises and conclusions
of the clauses.

A

B

C

O

P

A ∧ B ⇒ M

B ∧ C ⇒ N

M ∧ O ⇒ Q

N ∧ P ⇒ R

Q ∧ R ⇒ S

**Question 6:** Task environments:
Specify and describe the characteristics of the task environment
for an automated filling station attendant (filling gas tank,
checking and adding oil, and windshield washer fluid, and checking
tire pressures). For each characteristic (the six on page 43)
give an approximately two-sentence description of why you chose
the characteristic you did.