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
C00002 00002 .REQUIRE "SETUP2" SOURCE_FILE
.REQUIRE "SETUP2" SOURCE_FILE
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
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.
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).
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.
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
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.
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.
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.
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
10. Write a function to convert a list of English words to
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.
%3piglatin%5[(I LIKE LISP BETTER THAN PIG LATIN)] =
(I IKELAY ISPLAY ETTERBAY ANTHAY IGPAY ATINLAY)
%1there are two functions in LISP that you will need:
%3explode %5APPLE = (A P P L E)
%3readlist %5(A P P L E) = APPLE%1
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
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
%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.
%3match%5[(PLUS(TIMES X Y) Z), (PLUS ∪ (PLUS W Z))] =
((U . TIMES X Y)) (Z . PLUS W Z)))
%1where the single letters are regarded as variables.
13. The %3n%1th Fibonacci number is defined by the equations
%5F%60%5 = 1
F%61%5 = 1
F%6n+2%5 = F%6n+1%5 + F%6n%1.
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
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.
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.
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.