SICP

Exercise 2.65.    Use the results of exercises  2.63   and   2.64   to give   ( n ) implementations of   union-set   and   intersection-set   for sets implemented as (balanced) binary trees. 41 SOLUTION The code and tests are here .

Exercise 2.64.    The following procedure  list->tree  converts an ordered list to a balanced binary tree. The helper procedure  partial-tree  takes as arguments an integer  n  and list of at least  n  elements and constructs a balanced tree containing the first  n  elements of the list. The result returned by  partial-tree  is a pair (formed with  cons ) whose  car  is the constructed tree and whose  cdr  is the list of elements not included in the tree. (define (list->tree elements)   (car (partial-tree elements (length elements)))) (define (partial-tree elts n)   (if (= n 0)       (cons '() elts)       (let ((left-size (quotient (- n 1) 2)))         (let ((left-result (partial-tree elts left-size)))           (let ((left-tree (car left-result))                 (non-left-elts (cdr left-result))                 (right-size (- n (+ left-size 1))))             (let ((this-entry (car non-left-elts))                   (right-result (partial-tree (cdr non-left-elts)           

Exercise 2.63.   Each of the following two procedures converts a  binary tree to a list. (define (tree->list-1 tree)   (if (null? tree)       '()       (append (tree->list-1 (left-branch tree))               (cons (entry tree)                     (tree->list-1 (right-branch tree)))))) (define (tree->list-2 tree)   (define (copy-to-list tree result-list)     (if (null? tree)         result-list         (copy-to-list (left-branch tree)                       (cons (entry tree)                             (copy-to-list (right-branch tree)                                           result-list)))))   (copy-to-list tree '())) a. Do the two procedures produce the same result for every tree? If not, how do the results differ? What lists do the two procedures produce for the trees in figure  2.16 ? b. Do the two procedures have the same order of growth in the number of steps required to convert a balanced tree with  n  elements to a list? If not, which one grows more s

Exercise 2.62.   Give a   ( n ) implementation of   union-set   for sets represented as ordered lists. SOLUTION The code and tests are here .

Exercise 2.61.   Give an implementation of  adjoin-set  using the ordered representation. By analogy with  element-of-set?  show how to take advantage of the ordering to produce a procedure that requires on the average about half as many steps as with the unordered representation. SOLUTION The code and tests are here .

Exercise 2.60.   We specified that a set would be represented as a list with no duplicates. Now suppose we allow duplicates. For instance, the set {1,2,3} could be represented as the list   (2 3 2 1 3 2 2) . Design procedures   element-of-set? ,   adjoin-set ,   union-set , and   intersection-set   that operate on this representation. How does the efficiency of each compare with the corresponding procedure for the non-duplicate representation? Are there applications for which you would use this representation in preference to the non-duplicate one? SOLUTION The code and tests are here . Since we allow duplicates, the union operation is simple: just append one set to the other.  This procedure will have the performance characteristics of the primitive 'append' which  is Theta(n) where n is the number of elements in one of the sets (depending upon which set  'append' chooses to walk through to the end.) No change in the implementation of element-of-set?. When th

Exercise 2.59.   Implement the   union-set   operation for the unordered-list representation of sets. SOLUTION The code and tests are here .

Exercise 2.58.    Suppose we want to modify the differentiation program so that it works with ordinary mathematical notation, in which  +  and  *  are infix rather than prefix operators. Since the differentiation program is defined in terms of abstract data, we can modify it to work with different representations of expressions solely by changing the predicates, selectors, and constructors that define the representation of the algebraic expressions on which the differentiator is to operate. a. Show how to do this in order to differentiate algebraic expressions presented in infix form, such as  (x + (3 * (x + (y + 2)))) . To simplify the task, assume that  +  and  *  always take two arguments and that expressions are fully parenthesized. b. The problem becomes substantially harder if we allow standard algebraic notation, such as  (x + 3 * (x + y + 2)) , which drops unnecessary parentheses and assumes that multiplication is done before addition. Can you design appropriate predicates

Exercise 2.58.    Suppose we want to modify the differentiation program so that it works with ordinary mathematical notation, in which  +  and  *  are infix rather than prefix operators. Since the differentiation program is defined in terms of abstract data, we can modify it to work with different representations of expressions solely by changing the predicates, selectors, and constructors that define the representation of the algebraic expressions on which the differentiator is to operate. a. Show how to do this in order to differentiate algebraic expressions presented in infix form, such as  (x + (3 * (x + (y + 2)))) . To simplify the task, assume that  +  and  *  always take two arguments and that expressions are fully parenthesized. b. The problem becomes substantially harder if we allow standard algebraic notation, such as  (x + 3 * (x + y + 2)) , which drops unnecessary parentheses and assumes that multiplication is done before addition. Can you design appropriate predicates

Exercise 2.57.   Extend the differentiation program to handle sums and products of arbitrary numbers of (two or more) terms. Then the last example above could be expressed as (deriv '(* x y (+ x 3)) 'x) Try to do this by changing only the representation for sums and products, without changing the  deriv  procedure at all. For example, the  addend  of a sum would be the first term, and the  augend  would be the sum of the rest of the terms. SOLUTION The code and tests are here .

Exercise 2.56.    Show how to extend the basic differentiator to handle more kinds of expressions. For instance, implement the differentiation rule by adding a new clause to the  deriv  program and defining appropriate procedures  exponentiation? ,  base ,  exponent , and  make-exponentiation . (You may use the symbol  **  to denote exponentiation.) Build in the rules that anything raised to the power 0 is 1 and anything raised to the power 1 is the thing itself. SOLUTION The code and tests are here .

Exercise 2.55.   Eva Lu Ator types to the interpreter the expression (car ''abracadabra) To her surprise, the interpreter prints back  quote . Explain. SOLUTION The code and tests are here . ''abracadabra is actually '(quote abracadabra) is actually (quote (quote abracadabra)) This evaluates to a list of two elements, the first one being a single-quote and the  second one being the literal "abracadabra". So 'car' of this will evaluate to quote.  Naturally, 'cdr' of the same thing will evaluate to the single element list that  contains the literal abracadabra.

Exercise 2.54.   Two lists are said to be  equal?  if they contain equal elements arranged in the same order. For example, (equal? '(this is a list) '(this is a list)) is true, but (equal? '(this is a list) '(this (is a) list)) is false. To be more precise, we can define  equal?  recursively in terms of the basic  eq?  equality of symbols by saying that  a  and  b  are  equal?  if they are both symbols and the symbols are  eq? , or if they are both lists such that  (car a)  is  equal? to  (car b)  and  (cdr a)  is  equal?  to  (cdr b) . Using this idea, implement  equal?  as a procedure. 36 SOLUTION The code and tests are here .

Exercise 2.53.   What would the interpreter print in response to evaluating each of the following expressions? (list 'a 'b 'c) (list (list 'george)) (cdr '((x1 x2) (y1 y2))) (cadr '((x1 x2) (y1 y2))) (pair? (car '(a short list))) (memq 'red '((red shoes) (blue socks))) (memq 'red '(red shoes blue socks)) SOLUTION The code and tests are here .

Exercise 2.52.   Make changes to the square limit of  wave  shown in figure  2.9  by working at each of the levels described above. In particular: a.  Add some segments to the primitive  wave  painter of exercise   2.49  (to add a smile, for example). b.  Change the pattern constructed by  corner-split  (for example, by using only one copy of the  up-split  and  right-split  images instead of two). c.  Modify the version of  square-limit  that uses  square-of-four  so as to assemble the corners in a different pattern. (For example, you might make the big Mr. Rogers look outward from each corner of the square.) SOLUTION The code and tests are here . In this exercise, I have used the procedures from the included package. I have used  segments->painter directly from the package. I am also using transform-painter  directly from the package. The same is true for vector, segment and frame.  transform-painter is implemented slightly differently (see code)  from what is shown i

Exercise 2.51.   Define the   below   operation for painters.   Below   takes two painters as arguments. The resulting painter, given a frame, draws with the first painter in the bottom of the frame and with the second painter in the top. Define   below in two different ways -- first by writing a procedure that is analogous to the   beside   procedure given above, and again in terms of   beside   and suitable rotation operations (from exercise  2.50 ). SOLUTION The code and tests are here . In this exercise, I have used the procedures in the included package. I have used  segments->painter directly from the package. I am also using transform-painter  directly from the package. The same is true for vector, segment and frame.  transform-painter is implemented slightly differently (see code)  from what is shown in the text book. Accordingly, all other procedures like  wave-painter and frame-X-painter have been modified to work with the procedures  in the package.

Exercise 2.51.   Define the  below  operation for painters.  Below  takes two painters as arguments. The resulting painter, given a frame, draws with the first painter in the bottom of the frame and with the second painter in the top. Define  below  in two different ways -- first by writing a procedure that is analogous to the  beside  procedure given above, and again in terms of  beside  and suitable rotation operations (from exercise  2.50 ). SOLUTION The code and tests are here . Note: The implementation of the procedure segments->painter in the textbook  is different from the similarly named procedure in the sicp plt package. The plt package procedure takes a list of segments and draws them. Moreover,  this procedure draws segments only inside the unit square where 0 <= x,y <= 1. Any  points ouside the unit square are simply ignored (at least, there is no visual  output). The textbook implementation also takes a list of segments but instead of drawing them  di

Exercise 2.50.   Define the transformation  flip-horiz , which flips painters horizontally, and transformations that rotate painters counterclockwise by 180 degrees and 270 degrees. SOLUTION The code and tests are here . Note: I have modified 'transform-painter' and 'wave-painter' from the previous  exercise to make these work intuitively. Note: The implementation of the procedure segments->painter in the textbook  is different from the similarly named procedure in the sicp plt package. The plt package procedure takes a list of segments and draws them. Moreover,  this procedure draws segments only inside the unit square where 0 <= x,y <= 1. Any points ouside the unit square are simply ignored (at least, there is no visual output) The textbook implementation also takes a list of segments but instead of drawing them  directly, evaluates to a procedure that takes a frame as its input. This procedure when supplied with a frame, maps all the segments fr

Exercise 2.49.   Use  segments->painter  to define the following primitive painters: a.  The painter that draws the outline of the designated frame. b.  The painter that draws an ``X'' by connecting opposite corners of the frame. c.  The painter that draws a diamond shape by connecting the midpoints of the sides of the frame. d.  The  wave  painter. SOLUTION The code and tests are here . Note: The implementation of the procedure segments->painter in the textbook  is different from the similarly named procedure in the sicp plt package. The plt package procedure takes a list of segments and draws them. Moreover,  this procedure draws segments only inside the unit square where 0 <= x,y <= 1. Any  points ouside the unit square are simply ignored (at least, there is no visual  output) The textbook implementation also takes a list of segments but instead of drawing them  directly, evaluates to a procedure that takes a frame as its input.  This procedure

Exercise 2.48.    A directed line segment in the plane can be represented as a pair of vectors -- the vector running from the origin to the start-point of the segment, and the vector running from the origin to the end-point of the segment. Use your vector representation from exercise  2.46   to define a representation for segments with a constructor   make-segment   and selectors   start-segment   and   end-segment . SOLUTION The code and tests are here .

Exercise 2.47.   Here are two possible constructors for frames: (define (make-frame origin edge1 edge2)   (list origin edge1 edge2)) (define (make-frame origin edge1 edge2)   (cons origin (cons edge1 edge2))) For each constructor supply the appropriate selectors to produce an implementation for frames. SOLUTION The code and tests are here .

Exercise 2.46.    A two-dimensional vector  v  running from the origin to a point can be represented as a pair consisting of an  x -coordinate and a  y -coordinate. Implement a data abstraction for vectors by giving a constructor  make-vect  and corresponding selectors  xcor-vect  and  ycor-vect . In terms of your selectors and constructor, implement procedures  add-vect ,  sub-vect , and  scale-vect  that perform the operations vector addition, vector subtraction, and multiplying a vector by a scalar: SOLUTION The code and tests are here .