perm filename EXER[206,LSP]1 blob sn#127502 filedate 1974-10-28 generic text, type C, neo UTF8

COMMENT ⊗ VALID 00002 PAGES C REC PAGE DESCRIPTION C00001 00001 C00002 00002 .REQUIRE "SETUP2" SOURCE_FILE C00027 ENDMK C⊗; .REQUIRE "SETUP2" SOURCE_FILE .NEXT PAGE Exercises - CS206 Problems to be assigned will be selected from these. For problems 1 to 12, write Lisp functions as described. 1. %3alt%2[%3u, m, n%2]%1 takes every %3n%1th element of the list %3u%1 starting with the %3m%1th. Write a recursive defintion of %3alt%2[%3u, m, n%2].%1 .SKIP 2 2. %3odds u%1 is a list of the elements of the list %3u%1 that occur in %3u%1 an odd number of times. Write the fastest definition of %3odds %1 that you can. Give several if you like, but be sure to have one that works. .SKIP 2 3. %3commontail%2[%3u,v%2]%1 is the longest common sublist of %3u%1 and %3v%1 ending with the ends of the lists. Thus %3commontail%5[(A B C D E),(A C D E)] = (C D E). .SKIP 2 4. %3pairs%2[%3u,v%2]%1 is the list of all pairs of elements, each pair taking one element from %3u%1 and one from %3v%1. Thus %3pairs%5[(A B C),(D E)] = ((A D) (A E) (B D) (B E) (C D) (C E)).%1 Observe the ordering given in the example. .SKIP 2 5. a. %3rcycle%2[%3u%2]%1 is obtained from the list %3u%1 by moving the last element to the first position. Thus %3rcycle%5[(A B C D)] = (D A B C).%1 b. %3lcycle%2[%3u%2]%1 is obtained from the list %3u%1 by moving the first element to the last position. Thus %3lcycle%5[(A B C D)] = (B C D A).%1 .SKIP 2 6. %3permut u%1 is a list of all the permutations of the list %3u%1. Thus %3permut %5(A B C) = ((A B C)(A C B)(B A C)(B C A)(C A B)(C B A)). The order in which the permutations are listed is not important here. .SKIP 2 7. %3conn%2[%3g%2]%1 is true if and only if the directed graph %3g%1 represented as described in chapter 1 of the class notes is connected in the sense that every vertex is reachable from every other vertex. Write a LISP function for %3conn%1. .SKIP 2 8. Let a graph %3g%1 be described as in chapter 1 of the notes and suppose that whenever there is an edge from %3x%1 to %3y%1 there is also an edge from %3y%1 to %3x%1. 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. .SKIP 2 9. %3testr%2[%3u,f,p,w%2]%1 is obtained from the S-expression %3u%1 as follows: If no subexpression of %3u%1 satisfies the predicate %3p%1, then %3w%2[%3u%2]%1 is the result. If there is such an expression, say %3m%1, then %3f%2[%3m%2]%1 is the result. If there are several such %3m%1, then any %3f%2[%3m%2]%1 will do. .SKIP 2 10. Write a function to convert a list of English words to "Pig Latin." Each English word is translated to pig latin by the following rules: .BEGIN INDENT 8,8,0 1. if the first letter of the English word is a vowel then the pig latin translation is the same as the English word. 2. Otherwise, rotate the first letter of the word to the end of the word and repeat until the first letter becomes a vowel. Add the letters "AY" to the end of the word you have and that is the answer. 3. For the puposes of this problem, vowels are A E I O and U. 4. Assume every English word contains at least one vowel. .END .NOFILL example: %3piglatin%5[(I LIKE LISP BETTER THAN PIG LATIN)] = (I IKELAY ISPLAY ETTERBAY ANTHAY IGPAY ATINLAY) .FILL %1there are two functions in LISP that you will need: %3explode %5APPLE = (A P P L E) %1and %3readlist %5(A P P L E) = APPLE%1 .SKIP 2 11. Let the complex number %3x%2+%3iy%1 be represented as an S-expression by the pair (%3x . y%1); thus 3+4%3i%1 is represented as (3 . 4). Write an evaluator %3ceval%2[%3e%2]%1 where %3e%1 is an algebraic expression in PLUS, TIMES, and complex and real constants. For example, we have %3ceval%5[(PLUS (3 . 4) 7 (TIMES (1 . 2) (2 . 1)))] = (10 . 9).%1 .SKIP 2 12. Let %3u%1 and %3v%1 be two S-expressions. Certain of the atoms occurring in these expressions are regarded as variables, and the propositional expression %3isvar%2[%3x%2]%1 will be true if %3x%1 is a variable. %3%3u%1 and %3v%1 may be assumed to have no variables in common. If there are substitutions for the variables in %3u%1 and %3v%1 that make %3u%1 and %3v%1 the same expression, then %3match %2[%3u,v%2]%1 is a list of pairs such that %3e %2=%3sublis%2[%3match%2[%3u,v%2],%3u%2] = %3sublis%2[%3match%2[%3u,v%2],%3v%2]%1 for the most general %3e%1. Otherwise, %3match%2[%3u,v%2] = NO%1. For example, .NOFILL %3match%5[(PLUS(TIMES X Y) Z), (PLUS ∪ (PLUS W Z))] = ((U . TIMES X Y)) (Z . PLUS W Z))) .FILL %1where the single letters are regarded as variables. .SKIP 2 13. The %3n%1th Fibonacci number is defined by the equations .NOFILL %5F%60%5 = 1 F%61%5 = 1 F%6n+2%5 = F%6n+1%5 + F%6n%1. .FILL Thus we have F%62%5 = 2, F%63%5 = 3, F%64%5 = 5, F%65%5 = 8%1, etc. This definition translates into LISP as .NOFILL F%6n%2 ← %4if%3 n%2 = 0 %2∨ %3n%2 = 1 %4then%2 1 %4else%5 F%62n-2%2 + F%6n-1%1. What bad thing will happen if we try to compute F%6100%1 using this definition? Write a new LISP definition of F%6n%1 not suffering from this problem. .FILL .SKIP 2 14. Devise a list structure representation of positions in the game of tic-tac-toe (noughts and crosses), and write functions %3ter p%1, which tells whether the game is over in position %3p%1, %3imval p%1 which tells the value of the game for a terminated position (use -1, 0 and 1 for values), and %3successors p%1 which gives the successors to a non-terminating position %3p%1. Make no special effort to achieve efficiency. .SKIP 2 15. Compare the the compilation of %2∧%1's and %2∨%1'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.