Assignment 2 Solution

Questions




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


o T
R o
o


o C
T o E
A o


























o F
I o
A o D
H R E
o B






































L E
G o


B


C
o


H
T








o
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- rst 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))) (TFLE)



(BFS ’((R (I (G (H T)))))) (RIGHT)



(BFS ’(((A (B)) C (D)))) (CADB)



(BFS ’((T (H R E) E)))



(TEHRE)




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







1



(ABCDE)







This question aims to solve a problem stated by Homer Simpson in \Gone Maggie Gone", The Simp-sons, Season 20, Episode 13. 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 le hw2-skeleton.lsp contains a framework for solving this puzzle using depth- rst search. Im-plement the functions in it as described in the comments. DO NOT CHANGE THE FUNCTION NAMES OR PARAMETERS. DO NOT WRITE ANY ADDITIONAL FUNCTIONS.




Submission




Base your solution on the skeleton le named hw2-skeleton.lsp. Submit your commented LISP program in a le named hw2.lsp.




In a separate le named hw2.pdf submit a sample execution showing the values your program returns for the test cases given in the questions.




Submit .pdf on Gradescope, submit lisp le on CCLE.




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.), rst, second (third, etc.), rest, cons, list, append, length, numberp, listp, atom, symbolp, oddp, evenp, null, not, and, or, cond, equal, defun, let, let*, max, min, =, +, -, *, /. 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 speci ed 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 cor-rect skeleton of each. Some of these assignments are auto graded and having missing functions is problematic.




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







2






WITH YOUR ASSIGNMENT. ALL SOLUTIONS MUST BE WRITTEN UP INDE-PENDENTLY, 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 solu-tions 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 rst plagiarism o ense is suspension for one quarter. A second o ense usually results in dismissal from the University of California.








































































































































3