perm filename FINAL.F73[206,LSP]1 blob sn#365994 filedate 1978-07-06 generic text, type C, neo UTF8

COMMENT ⊗ VALID 00003 PAGES C REC PAGE DESCRIPTION C00001 00001 C00002 00002 \\M0BASL30\M1BASI30\M2SUB\M3NGR40\M4BDB30\. C00006 00003 \\M0BASL30\M1BASI30\M2SUB\M3NGR40\M4BDB30\. C00007 ENDMK C⊗; \\M0BASL30;\M1BASI30;\M2SUB;\M3NGR40;\M4BDB30;\. \F3\CCOMPUTER SCIENCE DEPARTMENT \CSTANFORD UNIVERSITY \CCS 206 COMPUTING WITH SYMBOLIC EXPRESSIONS FALL 1973 \CFINAL EXAM \F0\COpen Books and Notes \J1. \F1alt\F0[\F1u, m, n\F0] takes every \F1n\F0th element of the list \F1u\F0 starting with the \F1m\F0th. Write a recursive defintion of \F1alt\F0[\F1u, m, n\F0]. 2. \F1odds u\F0 is a list of the elements of the list \F1u\F0 that occur in \F1u\F0 an odd number of times. Write the fastest definition of \F1odds u\F0 that you can. Give several if you like, but be sure to have one that works. 3. Let a graph \F1g\F0 be described as in chapter 1 of the notes and suppose that whenever there is an edge from \F1x\F0 to \F1y\F0 there is also an edge from \F1y\F0 to \F1x\F0. A component of the graph is a collection of vertices which are all connected to each other by edge paths but not connected to any other vertices. Write a function to determine the number of components. 4. The \F1n\F0th Fibonacci number is defined by the equations\. F\F20\F0 = 1 F\F21\F0 = 1 F\F2n+2\F0 = F\F2n+1\F0 + F\F2n\F0. \JThus we have F\F22\F0 = 2, F\F23\F0 = 3, F\F24\F0 = 5, F\F25\F0 = 8, etc. This definition translates into LISP as\. F\F2n\F0 ← \F4if\F1 n\F0 = 0 \F4∨ \F1n\F0 = 1 \F4then\F0 1 \F4else\F0 F\F2n-2\F0 + F\F2n-1\F0. \J What bad thing will happen if we try to compute F\F2100\F0 using this definition? Write a new LISP definition of F\F2n\F0 not suffering from this problem. 5. Do \F4one\F0 of a and b. a. Compare the the compilation of ∧'s and ∨'s in LCOM0 and LCOM4. Give the simplest example you can of an expression for which LCOM4 generates better code indicating the code generated by each. b. The definition of \F1ter\F0 in TICTAC2.LSP is not very elegant and not very efficient. Essentially the same thing is done better in the definition of \F1win\F0. Revise \F1ter\F0 accordingly. Likewise revise \F1imval\F0.\. \\M0BASL30;\M1BASI30;\M2SUB;\M3NGR40;\M4BDB30;\. \F3\CCOMPUTER SCIENCE DEPARTMENT \CSTANFORD UNIVERSITY \CCS 206 COMPUTING WITH SYMBOLIC EXPRESSIONS FALL 1973 \CFINAL EXAM \CSolutions to Problems \F0 1. \F1alt[u,m,n] ← \F4if n \F1u \F4then \F0NIL \F4else if \F1m=1 \; \F4then a \F1u . alt[\F4d \F1u,n,n] \F4else \F1alt[\F4d \F1u,m-1,n].