Description
Questions
1. A search tree can be represented in LISP as follows:
(a) if the search tree contains a single leaf node L, it can be represented by atom L
(b) 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
L E
F
T
o
R o
I o
G o
H T
o
o
A o
B
o
D
C
o
T o
H R E
E
o
A o
o
C o
o
E
D
B
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))))
1
(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 (Santa’s 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.
Submission
• Submit all solution files on CCLE.
• Base your solution on the skeleton file named hw2-skeleton.lsp.
• Submit your commented LISP program in a file named hw2.lsp.
• In a separate file named hw2.txt submit a sample execution showing the values your program returns
for the test cases given in the questions.
• Your programs should be written in good style. In LISP, a comment is any characters following a
semicolon (;) on a line. Provide an overall comment explaining your solutions. Furthermore, every
function should have a header comment explaining precisely what its arguments are, and what value
it returns in terms of its arguments. In addition, you should use meaningful variable names.
• The physical layout of the code on the page is very important for making LISP programs readable.
Make sure that you use blank lines between functions and indent properly. Programming style will be
a consideration in grading the assignment.
• You are restricted to using the following functions, predicates, and operators: quote (’), car, cdr
(cadadr, etc.), first, second (third, etc.), rest, cons, list, append, length, numberp, listp, atom, symbolp,
oddp, evenp, null, not, and, or, cond, equal, defun, let, let*, =, +, -, *, /. Note: you are not permitted
to use mutable state (setq, setf, etc.) or last.
• You may assume that all input to your functions are legal; i.e. you do not need to validate inputs.
• Do not write any additional helper functions for your code unless this is explicitly allowed. Test
functions are OK.
• Your function declarations should look exactly as specified in this assignment. Make sure the
functions are spelled correctly, take the correct number of arguments, and those arguments are in the
correct order.
• Even if you are not able to implement working versions of these functions, please include a correct skeleton of each. Some of these assignments are auto graded and having missing functions is
problematic.
2
• By submitting this homework, you agree to the following honor code.
You are encouraged to work on your own in this class. If you get stuck, you may discuss the problem
with up to two other students, PROVIDED THAT YOU SUBMIT THEIR NAMES ALONG
WITH YOUR ASSIGNMENT. ALL SOLUTIONS MUST BE WRITTEN UP INDEPENDENTLY, HOWEVER. This means that you should never see another student’s solution
before submitting your own. You may always discuss any problem with me or the TAs. YOU MAY
NOT USE OLD SOLUTION SETS UNDER ANY CIRCUMSTANCES. Making your solutions available to other students, EVEN INADVERTENTLY (e.g., by keeping backups on github),
is aiding academic fraud, and will be treated as a violation of this honor code.
You are expected to subscribe to the highest standards of academic honesty. This means that every
idea that is not your own must be explicitly credited to its author. Failure to do this constitutes
plagiarism. Plagiarism includes using ideas, code, data, text, or analyses from any other students or
individuals, or any sources other than the course notes, without crediting these sources by name. Any
verbatim text that comes from another source must appear in quotes with the reference or citation
immediately following. Academic dishonesty will not be tolerated in this class. Any student suspected
of academic dishonesty will be reported to the Dean of Students. A typical penalty for a first plagiarism
offense is suspension for one quarter. A second offense usually results in dismissal from the University
of California.
3
