Assignment 1 Solution

Questions




This problem concerns the Padovan sequence. The rst few elements of the sequence are 1 1 1 2 2 3 4 5 7 9 12 16 21, . . . . The sequence is de ned as



PAD(n + 1) = PAD(n 1) + PAD(n 2)




with




PAD(0) = PAD(1) = PAD(2) = 1:




Write a single LISP function, called PAD, that takes a single integer argument N, and returns the Nth Padovan number. For example (PAD 5) returns 3, (PAD 3) returns 2, and (PAD 4) returns 2.




Test your program on at least the rst 10 Padovan numbers. Also test your program for larger values of N. What happens? Explain why in your hw1.pdf le.




Write a single LISP function, called SUMS, that takes a single numeric argument N, and returns the number of additions required by your PAD function to compute the Nth Padovan number. SUMS should not call PAD, but rather you should design the recursion for SUMS by examining your PAD code.



Test your program on at least the rst 10 values. What is the relationship between the values returned by PAD and SUMS? Explain why in you hw1.pdf le.




A tree can be represented in LISP as follows:



if the tree contains a single leaf node L, it can be represented by atom L



if the 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 ve trees.
















5
foo 3.1 -0.2




t
1
-0.2
r


foo
3.1
bar -0.2
f




i
l e




1 2 foo 3.1



g




h t













1






Their LISP representations are respectively (((l e ) f ) t ), (5 foo 3.1 -0.2), (1 (foo 3.1) -0.2), ( ((1 2) (foo 3.1)) (bar -0.2)), and (r ( i ( g ( h t)))).




Write a single LISP function, called ANON. It takes a single argument TREE that represents a tree, and returns an anonymized tree with the same structure, but where all symbols and numbers in the tree are replaced by a question mark. The anonymized versions of the trees above are as follows.













? ? ? ?

? ? ? ?




? ? ? ?

? ?




? ? ? ? ? ?




?




? ?




Test your program on at least these inputs:




(ANON ’42)



?




(ANON ’FOO)



?




(ANON ’(((L E) F) T))



(((? ?) ?) ?)




(ANON ’(5 FOO 3.1 -0.2)) (????)



(ANON ’(1 (FOO 3.1) -0.2)) (? (? ?) ?)



(ANON ’(((1 2) (FOO 3.1)) (BAR -0.2)))



(((? ?) (? ?)) (? ?))




(ANON ’(R (I (G (H T)))))



(? (? (? (? ?))))







Submission




Submit your commented LISP program in a le named hw1.lsp.




In a separate le named hw1.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.







2






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*, =, +, -, *, /. 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 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