perm filename MIDTER.S78[206,LSP]1 blob sn#352635 filedate 1978-05-03 generic text, type C, neo UTF8

COMMENT ⊗ VALID 00004 PAGES C REC PAGE DESCRIPTION C00001 00001 C00002 00002 .REQUIRE "LSPMAC.PUB[LSP,CLT]" source_file C00003 00003 .hd206 SPRING 1978 C00004 00004 #. The depth of an S-expression is given by the length of the longest C00008 ENDMK C⊗; .REQUIRE "LSPMAC.PUB[LSP,CLT]" source_file; . .MACRO hd206 (TERM) ⊂ .BEGIN NOFILL TURNON "←→" .place heading ←COMPUTER SCIENCE DEPARTMENT ←STANFORD UNIVERSITY .place text CS206 ←COMPUTING WITH SYMBOLIC EXPRESSIONS →TERM .TURNOFF .END ⊃ .LSPFONT .basicops .itemmac 1; . .PORTION MAINPORTION .hd206 SPRING 1978 .PAGE ← 1 .cb MIDTERM EXAM .ITEM←0 Write definitions for the following functions or predicates. You may use any books or notes that you wish on this test. You may use either external or internal notation for your definitions. .indent 0,4 #. The ⊗depth of an S-expression is given by the length of the longest path to an atom. Thus ⊗⊗depth[$$A$]=0⊗ and ⊗⊗depth[$$(((A.B).C).D)$]=3⊗. #. ⊗balanced[x] is true if and only if the S-expression is balanced. We say that an S-expression is balanced if it is an atom or if ⊗⊗depth[qa x]⊗ and ⊗⊗depth[qd x]⊗ differ by at most 1 and qa ⊗x and qd ⊗x are both balanced. Thus ⊗⊗balanced[$$((A.B).C)$]⊗ is true but ⊗⊗balanced[$$(((A.B).C).D)$]⊗ is false. #. Let ⊗g be an undirected graph represented as a list of lists as described in Chapter I. ##. ⊗deleteα_vertex[v,g] returns a graph ⊗g1 with vertices those of ⊗g omitting ⊗v, and edges the same as ⊗g omitting those connecting ⊗v to another vertex. .break ##. ⊗complement[g] returns a graph ⊗g1 with vertices the same as ⊗g, but vertices ⊗v and ⊗w are joined by an edge in ⊗g1 if and only if they are not joined by an edge in ⊗g. For example if ⊗g is given by $$((A_B_D)_(B_C_D_A)_(C_D_B)_(D_A_B_C))$ then we have: .begin nofill ⊗⊗deleteα_vertex[$$A$,g]=⊗$$((B_C_D)_(C_D_B)_(D_B_C))$ ⊗⊗ complement[g]=⊗$$((A_C)_(B)_(D)_(C_A))$. .end #. Consider arithmetic expressions as represented in Ch I. Namely an expression is .begin nofill (i) a number (satisfies ⊗numberp), (ii) a variable (not a number and satisfies qqat), (iii) a sum : $PLUS . < list of expressions > or (iv) a product : $TIMES . < list of expressions >. (For simplicity, assume the sum and product lists always have at least 2 elements.) .end The function ⊗sop converts such expressions into sum of products form, eg. the resulting expression is either a monomial or a sum of monomial terms which has the form $$PLUS$_._<list_of_monomials>. A monomial is either a number, a variable, or a product of the form $$TIMES$_._< list of numbers or variables >. Thus, .begin nofill ⊗⊗sop[$$(TIMES_(TIMES_X_3)_(PLUS_Y_Z)_(PLUS_Y_1))$]=⊗ $$(PLUS_(TIMES_X_3_Y_Y)_(TIMES_X_3_Y_1)_(TIMES_X_3_Z_Y)_(TIMES_X_3_Z_1))$. .end Notice that simplification is not required.