perm filename PROBS1.S78[206,LSP] blob sn#345809
filedate 1978-04-02 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00003 PAGES
C REC PAGE DESCRIPTION
C00002 00002 .REQUIRE "LSPMAC.PUB[LSP,CLT]" source_file
C00003 00003 .hd206 SPRING 1978
.REQUIRE "LSPMAC.PUB[LSP,CLT]" source_file;
.PAGE FRAME 56 HIGH 80 WIDE;
.evenleftborder ← oddleftborder ← 1000;
.area text lines 1 to 56;
.MACRO hd206 (TERM) ⊂
.BEGIN NOFILL TURNON "←→"
←COMPUTER SCIENCE DEPARTMENT
CS206 ←COMPUTING WITH SYMBOLIC EXPRESSIONS →TERM
.MACRO hw (NUMBER, DUEDATE) ⊂
. BEGIN TURNON "←" NOFILL
←PROBLEM SET NUMBER
. TURNOFF END ⊃
.hd206 SPRING 1978
.hw 1, |April 18|
Write LISP programs for each of the functions described below.
For each program turn in the following:
.begin nofill indent 12,12
#. The internal form of the program.
#. The corresponding external form recursive definition.
#. A description of how the progam works and why.
#. Output from test runs on a variety of input.
Late assignments are discouraged and will not be accepted after the
.bb Function descriptions.
.item ← 0
.BEGIN INDENT 0,6
#. ⊗allsub[u,v] returns a list giving all occurrences of the list ⊗u
as a toplevel sublist of ⊗v. An occurrence is given by the number
denoting the position in ⊗v where the match begins.
Thus ⊗⊗⊗allsub[$$(A A),(A A A A A)$] = $$(1 2 3 4)$.⊗
#. ⊗allsub![u,v] returns a list giving all occurrences of the list ⊗u
as a sublist of ⊗v, at any level. Now an occurrence is a list of numbers
giving the path to beginning to sublist occurrence.
Thus ⊗⊗⊗allsub![$$(A),(A (B (A (B (A)))))$] = $$((1) (2 2 1) (2 2 2 2 1))$⊗
#. ⊗mapexp takes as arguments an S-expression, a unary
function ⊗f1 and a binary function ⊗f2. It takes the S-expression apart,
applies the unary function to each atom and puts the result back
together using the binary function.
Thus if ⊗f1 is the identity function and ⊗f2 is ⊗cons then ⊗maptree returns
a copy of the S-expression. If ⊗f1 is ⊗ncons (forms a list of one element)
and ⊗f2 is ⊗append then ⊗maptree returns the ⊗fringe of the S-expression.
#. Let a graph ⊗g be represented as described in Chapter I of the text
and suppose that whenever there is an edge from ⊗x to ⊗y there is also
an edge from ⊗y to ⊗x. 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 vertices not in this collection. Write a function
⊗ncomps to determine the number of components of a graph ⊗g.
#. ⊗partition[u,n] is the list of partitions of the list ⊗u into
⊗n sublists ⊗u1, ... ⊗un such that ⊗⊗u1*[u2*...*un]=u⊗.
If ⊗n is greater than the length of ⊗u then your program should return
an error message of some kind.
⊗⊗⊗partition[$$(A B C),2$]=$$((A) (B C))((A B) (C)))$⊗
Write a program ⊗testpart to test the result returned by ⊗partition.
For each partition, ⊗testpart should append together the lists ⊗ui
and check that the result is ⊗u.