Questions

1. A search tree can be represented in LISP as follows:

• if the search tree contains a single leaf node L, it can be represented by atom L
• if the search tree has more than one node and is rooted at N, then it can be represented by a list (S1 S2 Sk) where Si represents the ith subtree of N.

Consider for example the following search trees, whose LISP representations are shown later.

o o o o o

C T E A

A H R EB

C

D

E

Write a single LISP function, called BFS. It takes a single argument FRINGE that represents a list of search trees, and returns a top-level list of leaf nodes, in the order they are visited by left-to-right breadth-first search. The inital call to BFS passes a FRINGE list with a single element: the root of the search tree.

Test your program on at least these inputs:

> (BFS (ROOT))

(ROOT)

> (BFS ((((L E) F) T)))

(T F L E)

> (BFS ((R (I (G (H T))))))

(R I G H T)

> (BFS (((A (B)) C (D))))

(C A D B)

> (BFS ((T (H R E) E)))

(T E H R E)

> (BFS ((A ((C ((E) D)) B))))

(A B C D E)

2. This question aims to solve a problem stated by Homer Simpson in Gone Maggie Gone, The Simpsons, Season 20, Episode 13. Watch the clip at http://www.simpsonsworld.com/video/313361987548. Homer wants to cross a river with his baby (Maggie), his dog (Santas Little Helper), and a jar of poison. Homer is the only one who can operate the boat, and he can take at most one thing with him. The dog cannot be left alone with the baby, because he tries to bite her. The baby cannot be left alone with the poison, because she tries to eat it. The goal is to get everybody on the other side of the river.

The file hw2-skeleton.lsp contains a framework for solving this puzzle using depth-first search. Implement the functions in it as described in the comments. DO NOT CHANGE THE FUNCTION

NAMES OR PARAMETERS. DO NOT WRITE ANY ADDITIONAL FUNCTIONS.

Extra: watch the clip at http://www.simpsonsworld.com/video/313359939855. It illustrates what happens when the search problem formulation ignores important details of the ill-defined real-world problem, and how the problem formulation is only an abstraction.