perm filename FINAL.F71[206,LSP] blob sn#005353 filedate 1971-12-15 generic text, type T, neo UTF8

00100 COMPUTER SCIENCE DEPARTMENT 00200 STANFORD UNIVERSITY 00300 00400 00500 CS 206 COMPUTING WITH SYMBOLIC EXPRESSIONS FALL 1971 00600 00700 00800 FINAL EXAMINATION 00900 open book and notes 01000 01005 01010 1. Let the complex number x+iy be represented as an S-expression 01015 by the pair (x . y); thus 3+4i is represented as (3 . 4). Write an 01020 evaluator ceval[e] where e is an algebraic expression in PLUS, TIMES, 01025 and complex and real constants. 01030 01035 For example, we have 01040 01045 ceval[(PLUS (3 . 4) 7 (TIMES (1 . 2) (2 . 1)))] = (10 . 9). 01047 01050 01100 2. conn[g] is true if and only if the directed graph g represented 01200 as described in chapter 1 of the class notes is connected in the sense 01300 that every vertex is reachable from every other vertex. Write a LISP 01400 function for conn. 01500 01600 01700 3. Let u and v be two S-expressions. Certain of the atoms 01800 occurring in these expressions are regarded as variables, and the 01900 propositional expression isvar[x] will be true if x is a variable. u 02000 and v may be assumed to have no variables in common. 02100 02200 If there are substitutions for the variables in u and v that 02300 make u and v the same expression, then match [u,v] is a list of pairs 02400 such that 02500 02600 e =sublis[match[u,v],u] = sublis[match[u,v],v] for the most 02700 02800 general e. Otherwise, match[u,v] = NO. 02900 03000 For example, 03100 03200 match[(PLUS(TIMES X Y) Z), (PLUS ∪ (PLUS W Z))] = 03300 ((U . TIMES X Y)) (Z . PLUS W Z))) 03400 03500 where the single letters are regarded as variables. 03600 05400 05500 4. Write a function to convert a list of English words to 05600 "Pig Latin." 05700 05800 Each English word is translated to pig latin by the following rules: 05900 06000 1. if the first letter of the English word is a vowel then the pig 06100 latin translation is the same as the English word. 06200 06300 2. Otherwise, rotate the first letter of the word to the end of the 06400 word and repeat until the first letter becomes a vowel. Add the 06500 letters "AY" to the end of the word you have and that is the answer. 06600 06700 3. For the puposes of this problem, vowels are A E I O and U. 06800 06900 4. Assume every English word contains at least one vowel. 07000 07100 07200 example: 07300 PIGLATIN('(I LIKE LISP BETTER THAN PIG LATIN)) = 07400 (I IKELAY ISPLAY ETTERBAY ANTHAY IGPAY ATINLAY) 07500 07600 there are two functions in LISP that you will need: 07700 07800 EXPLODE('APPLE) = '(A P P L E) 07900 and 08000 READLIST('(A P P L E)) = 'APPLE 08100