Structure and Interpretation of Computer Programs

Once again I did all of the questions and I'm going to continue to do that. It seems pointless to skip exercises even though they aren't needed for this course; the whole reason for going through the book is to learn. Not sure if my reasoning is always right though. Again, there is a lot of material in the exercises so this time, rather than create a massive post here I posted my answers to pastebin.com for everyone to look at.

Ex 2.53

(list 'a 'b 'c)
-> (a b c)
(list (list 'george))
-> ((george))
(cdr '((x1 x2) (y1 y2)))
-> ((y1 y2))
(cadr '((x1 x2) (y1 y2)))
-> (y1 y2)
(pair? (car '(a short list)))
-> #f
(memq 'red '((red shoes) (blue socks)))
-> #f
(memq 'red '(red shoes blue socks))
-> (red shoes blue socks)

Ex 2.55

' is shorthand for the procedure quote which creates a constant value so

''abracadabra is equivalent to (quote (quote abracadabra))

which results on the literal list '(quote abracadabra) consisting of 2 symbols 'quote and 'abracadabra so

(car ''abracadabra)

(car '(quote abracadabra))

'quote

Ex 2.60

time efficiency

element-of-set O(n) - we have to adjoin-set O(n) - due to using element-of-set intersection-set O(n^2) - for each element in the first set we execute element-of-set against the 2nd union-set O(n^2) - for each element in the first set we execute element-of-set against the 2nd element-of-set-dup O(n) - identical adjoin-set-dup O(1) - more efficient intersection-set-dup O(n^2) - identical union-set-dup O(n) - however the built in append will presumably be optimised

space efficiency

All of the new procedures will use at least if not more space as the non duplicates

It's hard to give a definitive answer. I'd use the duplicate representation primarily if the application's demands them to be important. e.g. Counting aces in a tennis match Is saving space more important than processing time on large sets? Unlikely these days, but if so use the original Is speed of processing largish sets more important? Use the new representation

Ex 2.63a Both tree->list-1 and tree->list-2 result in the same lists

Ex 2.63b tree->list1 visits each tree item once and at each visit it uses append so its growth is O(append.n) Assuming a balanced tree then O(append) will be O(n/2 + n/4 + n/8 ...) = O(log n) So tree->list1 is O(n.log n)

tree->list2 tree->list2 visits each tree item once and at each visit it uses cons so its growth is O(1.n) = O(n)

Ex 2.64a (partial-tree ''(1 3 5 7 9 11) 2)

partial tree has 3 main actions:

1. It makes a recursive call to partial tree which returns:

   tree of the first half of the sorted list

   the remaining elements the second half of the initial list

2. Remove the first of the remaining elements to form the root of the complete tree

3. Make a recursive call to partial tree with the rest of th eremaining elements.

The items generated by 1,2 and 3 are used to construct a tree made of all the items in the initial list (list->tree '(1 3 5 7 9 11)

               5
              / \
             1   \
              \   \
               3   9
                  / \
                 7   11

Ex 2.64b list->tree makes a single call to partial tree:

partial tree makes 2 calls to partial tree - each with (floor n/2) elements therefore for a list of n

1. 1 + sl1(n/2) + sr1(n/2) -> 2

sl1(n/2) sl2(n/4) + sr2(n/4) -> 2

sr2(n/2) sr3(n/8) + sr2(n/8) -> 2

each step reduces the problem set by half but makes 2 calls so the growth is O(n)

Ex 2.70

(length (encode song lyric-tree))
-> 84

the minimum number of bits needed per token is ln2 length alphabet so the song will need

(* (log-base-n (length lyric-pairs) 2) (length song))
-> 108 bits

Ex 2.71

n = 5

              (ABCDE 31)

             /          \

            (ABCD 15)  (E 16)

           /         \

         (ABC 7)    (D 8)

        /       \

     (AB 3)    (C 4)

     /     \

  (A 1)   (B 2)

n = 10

                  (ABCDEFGHIJ 1023)

                 /                 \

                (ABCDEFGHI 511)     (J 512)

               /               \

              (ABCDEFGH 255)    (I 256)

             /              \

            (ABCDEFG 127)    (H 128)

           /             \

          (ABCDEF 63)     (G 64)

         /           \

        (ABCDE 31)    (F 32)

       /          \

      (ABCD 15)    (E 16)

     /         \

    (ABC 7)     (D 8)

   /       \

  (AB 3)    (C 4)

 /      \

(A 1)   (B 2)

The encoding length for the most frequent will be 1.

The encoding length for the least frequent will be the depth of the tree constructed = n-1.

Ex 2.72 Growth for encode is t * d where

t is the number of tokens at particular tree level and

d is the height / depth of the tree.

For a tree of n token, t is range 1..n so the growth is O(n)

For a balanced tree d is lg n and unbalanced t is n-1

t is in range lgn .. n-1 and so has growht of O(n)

Encode therefore has growth in the range O(lg n).. O(n^2)

and so by convention we take the large O(n^2)

;; Exercise 2.55

Reading the quote operator works from left to right, so (car '(quote abracadabra)) is quote.

;; Exercise 2.63

tree->list-1 is a recursive process with time proportional to the number of elements, and space required proportional to the number of elements.

In tree->list-2, each node is visted only once with a procedure that collects elements to the left of the node and a procedure that collects elements to the right of the node. The same technique that is used in tree->list-1.

There is no difference between the orders of growth in either of them.

Exercise 2.67

(a d a b b c a)

Exercise 2.71

The most frequent symbol is encoded in 1 bit and the least frequent in n-1 bits