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
```