Monday, January 12, 2009

SICP Section 2.3 Symbolic Data

Exercise 2.53. What would the interpreter print in response to evaluating each of the following expressions?


Exercise 2.54. Two lists are said to be equal? if they contain equal elements arranged in the same order. For example,

is true, but

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.


Exercise 2.55. Eva Lu Ator types to the interpreter the expression

To her surprise, the interpreter prints back quote. Explain.

Answer: It is easier to understand what happens if we replace the inner ' character with the quote operation. The expression now becomes:

This is possible since the ' character is just an easy abbreviation for quote. As the first entity in the list is quote, car returns quote.

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.


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

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.


Exercise 2.59. Implement the union-set operation for the unordered-list representation of sets.


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?

Answer: Element-of-set? is unchanged from above.

Adjoin-set no longer needs to check for element-of-set?. This version of adjoin-set is O(1) (compared to O(n) earlier).

Union-set no longer needs to check for element-of-set?. This version of union-set is O(n) (compared to O(n^2) earlier)

Intersection-set remains unchanged.

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.


Exercise 2.63. Each of the following two procedures converts a binary tree to a list.

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 slowly?

Answer: a. Both procedures produce same results for all trees.

b. Both procedures have identical orders of growth. Both procedures solve the problem in O(n) steps.

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.


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.


Exercise 2.67. Define an encoding tree and a sample message:

Use the decode procedure to decode the message, and give the result.


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.

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.


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.

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


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

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?


As there are 8 different symbols we will need log2(8) = 3 bits per alphabet for encoding. There are 36 different alphabets in the message which require 36 * 3 = 108 bits for encoding.

No comments: