SICP

Exercise 2.75.    Implement the constructor   make-from-mag-ang   in message-passing style. This procedure should be analogous to the   make-from-real-imag   procedure given above. SOLUTION The code and tests are here .

Exercise 2.74.    Insatiable Enterprises, Inc., is a highly decentralized conglomerate company consisting of a large number of independent divisions located all over the world. The company's computer facilities have just been interconnected by means of a clever network-interfacing scheme that makes the entire network appear to any user to be a single computer. Insatiable's president, in her first attempt to exploit the ability of the network to extract administrative information from division files, is dismayed to discover that, although all the division files have been implemented as data structures in Scheme, the particular data structure used varies from division to division. A meeting of division managers is hastily called to search for a strategy to integrate the files that will satisfy headquarters' needs while preserving the existing autonomy of the divisions. Show how such a strategy can be implemented with data-directed programming. As an example, suppose that e...

Exercise 2.74.    Insatiable Enterprises, Inc., is a highly decentralized conglomerate company consisting of a large number of independent divisions located all over the world. The company's computer facilities have just been interconnected by means of a clever network-interfacing scheme that makes the entire network appear to any user to be a single computer. Insatiable's president, in her first attempt to exploit the ability of the network to extract administrative information from division files, is dismayed to discover that, although all the division files have been implemented as data structures in Scheme, the particular data structure used varies from division to division. A meeting of division managers is hastily called to search for a strategy to integrate the files that will satisfy headquarters' needs while preserving the existing autonomy of the divisions. Show how such a strategy can be implemented with data-directed programming. As an example, suppose that ...

Exercise 2.73.   Section  2.3.2  described a program that performs symbolic differentiation: (define (deriv exp var)   (cond ((number? exp) 0)         ((variable? exp) (if (same-variable? exp var) 1 0))         ((sum? exp)          (make-sum (deriv (addend exp) var)                    (deriv (augend exp) var)))         ((product? exp)          (make-sum            (make-product (multiplier exp)                ...

Exercise 2.73.   Section  2.3.2  described a program that performs symbolic differentiation: (define (deriv exp var)   (cond ((number? exp) 0)         ((variable? exp) (if (same-variable? exp var) 1 0))         ((sum? exp)          (make-sum (deriv (addend exp) var)                    (deriv (augend exp) var)))         ((product? exp)          (make-sum            (make-product (multiplier exp)                ...

Exercise 2.73.  Section 2.3.2 described a program that performs symbolic differentiation: (define (deriv exp var)   (cond ((number? exp) 0)         ((variable? exp) (if (same-variable? exp var) 1 0))         ((sum? exp)          (make-sum (deriv (addend exp) var)                    (deriv (augend exp) var)))         ((product? exp)          (make-sum            (make-product (multiplier exp)                          (deriv (multiplicand exp) var))            (make-product (deriv (multiplier exp) var)                          (multiplicand exp))))         <more rules can be added here>   ...

Exercise 2.72.    Consider the encoding procedure that you designed in exercise  2.68 . What is the order of growth in the number of steps needed to encode a symbol? Be sure to include the number of steps needed to search the symbol list at each node encountered. To answer this question in general is difficult. Consider the special case where the relative frequencies of the  n  symbols are as described in exercise  2.71 , and give the order of growth (as a function of  n ) of the number of steps needed to encode the most frequent and least frequent symbols in the alphabet. Answer: The 'encode-symbol' procedure starts at the root of the huffman encoding tree and walks down the tree to find the symbol we are interested in. At each node it calls 'element-of-set?' potentially twice to determine the branch in which the symbol exists. 'element-of-set?' has an order of growth of O(n) where n is the number of elements in the set. Note that this order of...

Exercise 2.71.   Suppose we have a Huffman tree for an alphabet of   n   symbols, and that the relative frequencies of the symbols are 1, 2, 4,   ... , 2 n -1 . Sketch the tree for   n =5; for   n =10. In such a tree (for general   n ) how many bits are required to encode the most frequent symbol? the least frequent symbol?

Exercise 2.70.    The following eight-symbol alphabet with associated relative frequencies was designed to efficiently encode the lyrics of 1950s rock songs. (Note that the ``symbols'' of an ``alphabet'' need not be individual letters.) A 2 NA 16 BOOM 1 SHA 3 GET 2 YIP 9 JOB 2 WAH 1 Use  generate-huffman-tree  (exercise  2.69 ) to generate a corresponding Huffman tree, and use  encode  (exercise  2.68 ) to encode the following message: Get a job Sha na na na na na na na na Get a job Sha na na na na na na na na Wah yip yip yip yip yip yip yip yip yip Sha boom How many bits are required for the encoding? What is the smallest number of bits that would be needed to encode this song if we used a fixed-length code for the eight-symbol alphabet? SOLUTION The code and tests are here . Encoding tree is:  ((leaf NA 16) ((leaf YIP 9) (((leaf A 2) ((leaf WAH 1) (leaf BOOM 1) (WAH BOOM) 2) (A WAH BOOM) 4) ((leaf SHA 3) ((leaf JO...

Exercise 2.69.   The following procedure takes as its argument a list of symbol-frequency pairs (where no symbol appears in more than one pair) and generates a Huffman encoding tree according to the Huffman algorithm. (define (generate-huffman-tree pairs)   (successive-merge (make-leaf-set pairs))) Make-leaf-set  is the procedure given above that transforms the list of pairs into an ordered set of leaves.  Successive-merge  is the procedure you must write, using  make-code-tree  to successively merge the smallest-weight elements of the set until there is only one element left, which is the desired Huffman tree. (This procedure is slightly tricky, but not really complicated. If you find yourself designing a complex procedure, then you are almost certainly doing something wrong. You can take significant advantage of the fact that we are using an ordered set representation.) SOLUTION The code and tests are here . ...

Exercise 2.68.   The  encode  procedure takes as arguments a message and a tree and produces the list of bits that gives the encoded message. (define (encode message tree)   (if (null? message)       '()       (append (encode-symbol (car message) tree)               (encode (cdr message) tree)))) Encode-symbol  is a procedure, which you must write, that returns the list of bits that encodes a given symbol according to a given tree. You should design  encode-symbol  so that it signals an error if the symbol is not in the tree at all. Test your procedure by encoding the result you obtained in exercise  2.67  with the sample tree and seeing whether it is the same as the original sample message. SOLUTION The code and tests are here .

Exercise 2.67.   Define an encoding tree and a sample message: (define sample-tree   (make-code-tree (make-leaf 'A 4)                   (make-code-tree                    (make-leaf 'B 2)                    (make-code-tree (make-leaf 'D 1)                                    (make-leaf 'C 1))))) (define sample-message '(0 1 1 0 0 1 0 1 0 1 1 1 0)) Use the  decode  procedure to decode ...

Exercise 2.66.   Implement the  lookup  procedure for the case where the set of records is structured as a binary tree, ordered by the numerical values of the keys. SOLUTION The code and tests are here .

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...

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)              ...

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 imple...

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