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 C00001 00001 C00002 00002 .REQUIRE "LSPMAC.PUB[LSP,CLT]" source_file C00003 00003 .hd206 SPRING 1978 C00008 ENDMK C⊗; .REQUIRE "LSPMAC.PUB[LSP,CLT]" source_file; .PAGE FRAME 56 HIGH 80 WIDE; .evenleftborder ← oddleftborder ← 1000; .area text lines 1 to 56; .place text; . .MACRO hd206 (TERM) ⊂ .BEGIN NOFILL TURNON "←→" ←COMPUTER SCIENCE DEPARTMENT ←STANFORD UNIVERSITY .SKIP CS206 ←COMPUTING WITH SYMBOLIC EXPRESSIONS →TERM .TURNOFF .END ⊃ . . .MACRO hw (NUMBER, DUEDATE) ⊂ . BEGIN TURNON "←" NOFILL ←PROBLEM SET NUMBER ←Due DUEDATE . TURNOFF END ⊃ . .itemmac . .PORTION MAINPORTION . .hd206 SPRING 1978 .skip .hw 1, |April 18| Write LISP programs for each of the functions described below. For each program turn in the following: .item←0 .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. .end Late assignments are discouraged and will not be accepted after the solutions appear. .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. Thus ⊗⊗⊗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. .END