#93/111: Concrete Abstractions

Following the other basic books I wanted to strengthen my basic knowledge about computer science and this book is excellent for this task. It uses Scheme as the introductory language (like SICP) and does a great job in explaining basic data structures and algorithms. If you want to seriously learn about basic computer science, this is a nice book which is also a bit easy than SICP. You can actually read Concrete Abstractions for free which is quite nice.

Concrete Abstractions: Chapter 12

Exercise 12.4: Draw a tree, analogous to Figure 4.4 on page 92, showing how the value of C(4, 2) is computed by choose. Your tree should have C(4, 2) at the root and six 1s as its leaves.
Solution:

Exercise 12.6: Using these procedures, write
a. A procedure called table-fill! that takes a table and an element and sets every entry in the table to the given element. For example, (table-fill! table 0) would have a similar effect to that of zero-out-vector! in Section 11.6.
b. A procedure called display-table that nicely displays its table parameter.

Solution:

(define table-fill!
  (lambda (table value)
    (define loop-row
      (lambda (row column)
        (if (= column (table-width table))
            'done
            (begin
              (table-set! table row column value)
              (loop-row row (+ column 1))))))
    (define loop
      (lambda (row)
        (if (= row (table-height table))
            'done
            (begin
              (loop-row row 0)
              (loop (+ row 1))))))
    (loop 0)))

b.

(define display-table
  (lambda (table)
    (define show-row
      (lambda (row column)
        (if (= column (table-width table))
            (newline)
            (begin
              (display (table-ref table row column))
              (display " ")
              (show-row row (+ column 1))))))
    (define show
      (lambda (row)
        (if (= row (table-height table))
            (newline)
            (begin
              (show-row row 0)
              (show (+ row 1))))))
    (show 0)))

Exercise 12.31: Imagine the following game: You are given a path that consists of white and black squares. The exact configuration of white and black squares varies with the game. You start on the leftmost square (which we’ll call square 0), and your goal is to move off the right end of the path in the least number of moves. However, the rules stipulate that:
If you are on a white square, you can move either 1 or 2 squares to the right.
If you are on a black square, you can move either 1 or 4 squares to the right. […]
Write a memoized version of fewest-moves.
Solution:

(define fewest-moves-mem
  (lambda (path)
    (let ((table (make-vector (vector-length path))))
      (define fewest-moves-f
        (lambda (path i)
          (cond ((>= i (vector-length path))
                 0)
                ((equal? (vector-ref path i) 'white)
                 (+ 1 (min (fewest-moves-sub path (+ i 1))
                           (fewest-moves-sub path (+ i 2)))))
                (else
                 (+ 1 (min (fewest-moves-sub path (+ i 1))
                           (fewest-moves-sub path (+ i 4))))))))

      (define fewest-moves-sub
        (lambda (path i)
          (ensure-in-table! path i)
          (vector-ref table i)))

      (define ensure-in-table!
        (lambda (path i)
          (if (vector-ref table i)
              'done
              (store-in-table! table i))))

      (define store-in-table!
        (lambda (table i)
          (vector-set! table i (fewest-moves path i))))

      (vector-fill! table #f)

      (fewest-moves-f path 0))))

Exercise 12.33: The function h(n) is defined for nonnegative integers n as follows:
h(n) = \begin{cases} 1 & \text{ if } n<2\\ h(n-1) + h(n-2) & \text{ if n } < \text{2 and n is odd}\\ h(n-1) + h(n/2) & \text{ if n } \geq \text{2 and n is even}\\ \end{cases}
a. Write a dynamic programming procedure for efficiently calculating h(n).
b. Is it possible to modify the procedure so that it stores all the values it needs in a vector of fixed size, as walk-count can be modified to store the values it needs in a two-element vector? (A vector of “fixed size” is one with a size that does not depend on the parameter, n.) Justify your answer.
Solution: a & b. I implemented b directly into the code.

(define h
  (lambda (n)
    (let ((vector (make-vector (+ n 1))))
      (define calc-h
        (lambda (n)
          (cond ((< n 2) 1)
                ((odd? n) (+
                           (calc-h-sub (- n 1))
                           (calc-h-sub (- n 2))))
                (else (+
                       (calc-h-sub (- n 1))
                       (calc-h-sub (/ n 2)))))))

      (define calc-h-sub
        (lambda (n)
          (vector-ref vector n)))

      (from-to-do 0 n
                  (lambda (i)
                    (vector-set! vector i (calc-h i))))

      (calc-h n))))

Concrete Abstractions: Chapter 8

Exercise 8.1: Write a procedure called minimum that will find the smallest element in a nonempty binary search tree of numbers.

Solution:

(define minimum
  (lambda (tree)
    (if (empty-tree? (left-subtree tree))
        (root tree)
        (minimum (left-subtree tree)))))

Exercise 8.2: Write a procedure called number-of-nodes that will count the number of elements in a binary search tree.

Solution:

(define number-of-nodes
  (lambda (tree)
    (if (empty-tree? tree)
        0
        (+ 1 
           (number-of-nodes (left-subtree tree))
           (number-of-nodes (right-subtree tree))))))

Exercise 8.6: Suppose we want to create a new binary search tree by adding another element to an already existing binary search tree. Where is the easiest place to add such an element? Write a procedure called insert that takes a number and a binary search tree of numbers and returns a new binary search tree whose elements consist of the given number together with all of the elements of the binary search tree. You may assume that the given number isn’t already in the tree.

Solution:

(define insert
  (lambda (tree x)
    (if (empty-tree? tree)
        (make-nonempty-tree x '() '())
    (cond ((< x (root tree))
           (make-nonempty-tree 
            (root tree) (insert (left-subtree tree) x) (right-subtree tree)))
          ((> x (root tree))
           (make-nonempty-tree
            (root tree ) (left-subtree tree) (insert (right-subtree tree) x)))))))

Exercise 8.7: Using the procedure insert, write a procedure called list->bstree that takes a list of numbers and returns a binary tree whose elements are those numbers. Try this on several different lists and draw the corresponding tree diagrams. What kind of list gives you a short bushy tree? What kind of list gives a tall skinny tree?

Solution:

(define list->bstree
  (lambda (lst)
    (if (null? lst)
        (make-empty-tree)
        (insert (list->bstree (cdr lst)) (car lst)))))

Exercise 8.11: In many applications, binary trees aren’t sufficient because we need more than two subtrees. An m-ary tree is a tree that is either empty or has a root and m subtrees, each of which is an m-ary tree. Generalize the previous results to m-ary trees.

Solution:
Ok. So let’s see if we can find a formular for 3-ary trees first.

So we can see that a tree with an height of two has 3^2 + 3^1 + 3^0 nodes. Or more general: A 3-ary tree with an height of n has sum_{i=0}^{n} 3^i nodes. This can be simplified as frac{1 - 3^{n+1}}{1-3}. So is this true? Let’s see. The height should be n. What’s happening if we increase the height by one? Each leave will get three children. We assumed that there are 3^n leaves. Therefore there will be 3^n * 3 = 3^{n+1} children. That is, there will be at most text{nodes}(n+1) = text{nodes}(n) + 3^{n+1} nodes which is equivalent to sum_{i=0}^{n} 3^i + 3^{n+1} = sum_{i=0}^{n+1} 3^i.
Therefore there are sum_{i=0}^{n} m^i nodes in a m-ary of height n.

Exercise 8.12: In Exercise 8.7, you wrote a procedure list->bstree that created a binary search tree from a list by successively inserting the elements into the tree. This procedure can lead to trees that are far from minimum height—surprisingly, the worst case occurs if the list is in sorted order. However, if you know the list is already in sorted order, you can do much better: Write a procedure sorted-list->min-height-bstree that creates a minimum height binary search tree from a sorted list of numbers. Hint: If the list has more than one element, split it into three parts: the middle element, the elements before the middle element, and the elements after. Construct the whole tree by making the appropriate recursive calls on these sublists and combining the results.

Solution:

(define sorted-list->min-height-bstree
  (lambda (lst)
    (if (null? lst)
        (make-empty-tree)
        (if (not (list? lst))
            lst
            (make-nonempty-tree (middle-item lst) 
                                (sorted-list->min-height-bstree (left-items lst)) 
                                (sorted-list->min-height-bstree (right-items lst)))))))


(define list-element-range
  (lambda (lst start end i)
    (if (null? lst)
        '()
        (cond ((> i end)
               '())
              ((= i end)
               (cons (car lst) (list-element-range '() start end (+ i 1))))
              ((or (= i start) (> i start))
               (cons (car lst) (list-element-range (cdr lst) start end (+ i 1))))
              (else
               (list-element-range (cdr lst) start end (+ i 1)))))))

(define middle-item
  (lambda (lst)
    (let ((len (length lst)))
      (if (even? len)
        (list-element-range lst (/ len 2) (/ len 2) 0)
        (list-element-range lst (- (/ (+ len 1) 2) 1) (- (/ (+ len 1) 2) 1) 0)))))

(define left-items
  (lambda (lst)
    (let ((len (length lst)))
          (if (even? len)
              (list-element-range lst 0 (- (/ len 2) 1) 0)
              (list-element-range lst 0 (- (/ (+ len 1) 2) 2) 0)))))

(define right-items
  (lambda (lst)
    (let ((len (length lst)))
          (if (even? len)
              (list-element-range lst (+ 1 (/ len 2)) (+ len 1) 0)
              (list-element-range lst (/ (+ len 1) 2) len 0)))))

Exercise 8.31: Write a procedure that takes as arguments a binary search tree of numbers, a lower bound, and an upper bound and counts how many elements of the tree are greater than or equal to the lower bound and less than or equal to the upper bound. Assume that the tree may contain duplicate elements. Make sure your procedure doesn’t examine more of the tree than is necessary.

Solution:

(define count-elements-in-boundary
   (lambda (tree lower upper)
     (if (empty-tree? tree)
         0
         (+ 
          (if (or (< (root tree) lower) (> (root tree) upper))
             0
             1) 
          (count-elements-in-boundary (left-subtree tree) lower upper)
          (count-elements-in-boundary (right-subtree tree) lower upper)))))
     

Concrete Abstractions: Chapter 7

Exercise 7.5 Generalize sum to a higher-order procedure that can accumulate together the elements of a list in an arbitrary fashion by using a combining procedure (such as +) specified by a procedural parameter. When the list is empty, sum returned 0, but this result isn’t appropriate for other combining procedures. For example, if the com- bining procedure is *, 1 would be the appropriate value for an empty list. (Why?) Following are two possible approaches to this problem:
a. Write the higher-order procedure so that it only works for nonempty lists. That way, the base case can be for one-element lists, in which case the one element can be returned.
b. Write the higher-order procedure so that it takes an additional argument, beyond the list and the combining procedure, that specifies the value to return for an empty list.

Solution:
a.

(define accumulate-lst
  (lambda (lst f)
    (if (= (length lst) 1)
      (f (car lst))
      (f (car lst) (accumulate-lst (cdr lst) f)))))

; b.

(define accumulate-lst-base
  (lambda (lst f b)
    (if (null? lst)
      b
      (f (car lst) (accumulate-lst-base (cdr lst) f b)))))

Exercise 7.6 a. Write a procedure that will count the number of times a particular element occurs in a given list.
b. Generalize this procedure to one that will count the number of elements in a given list that satisfy a given predicate.

Solution:

(define count-elements
  (lambda (lst pred)
    (if (null? lst)
      0
      (if (pred (car lst))
        (+ 1 (count-elements (cdr lst) pred))
        (+ 0 (count-elements (cdr lst) pred))))))

Exercise 7.13: The procedure map is extraordinarily handy for creating lists of all sorts. Each of the following problems can be solved by using map.
a. Write a procedure that, when given a positive integer n, returns a list of the first n perfect squares.
b. Write a procedure that, when given a positive integer n, returns a list of the first n even integers.
c. Write a procedure called sevens that, when given a positive integer n, returns a list of n sevens. For example:

(sevens 5)

d. Write a procedure that, when given a list of positive integers, returns a list of lists of integers. Each of these lists should be the positive integers from 1 to whatever was in the original list. For example,

(list-of-lists ’(1 5 3))
((1) (1 2 3 4 5) (1 2 3))

Solution:
a.

(define first-n-perfect-squares
  (lambda (n)
    (map (lambda (x) (* x x)) (integers-from-to 1 n))))

b.

(define first-n-even-integers
  (lambda (n)
    (map (lambda (x) (* x 2)) (integers-from-to 1 n))))

c.

(define sevens
  (lambda (n)
    (map (lambda (x) 7) (integers-from-to 1 n))))

d.

(define list-of-lists
  (lambda (lst)
    (map (lambda (n) (integers-from-to 1 n)) lst)))

Ex 7.14

(define my-map
  (lambda (f lst)
    (if (null? lst)
      '()
      (cons (f (car lst)) (my-map f (cdr lst))))))

Exercise 7.42: Write a procedure called apply-all that, when given a list of functions and a number, will produce the list of the values of the functions when applied to the number.

Solution:

(define apply-all
  (lambda (funs x)
    (if (null? funs)
      '()
      (cons ((car funs) x) (apply-all (cdr funs) x)))))

Exercise 7.44: Consider the following two procedures. The procedure last selects the last element from a list, which must be nonempty. It uses length to find the length of the list.

(define last
  (lambda (lst)
    (if (= (length lst) 1)
      (car lst)
      (last (cdr lst)))))</code>

(define length
  (lambda (lst)
    (if (null? lst)
      0
      (+ 1 (length (cdr lst))))))

a. How many cdrs does (length lst) do when lst has n elements?
b. How many calls to length does (last lst) make when lst has n elements?
c. Express in Theta notation the total number of cdrs done by (last lst), including cdrs done by length, again assuming that lst has n elements.
d. Give an exact formula for the total number of cdrs done by (last lst), including cdrs done by length, again assuming that lst has n elements.

Solution:
a. n, which can be easily seen. An empty list needs 0 cdrs, a list with length 1 needs one cdrs. If we use induction, we can assume that this holds. For a list of length (n+1), we can see that length uses one cdr and then generates (length ). Therefore there are n uses of cdr for a list of length n.
b. Let’s start with the base case. (last ‘(1)) here last calls length one time. We can see that each time last have to call length. Therefore we can see that it needs n calls for a list of length n. The idea of the proof follows the last one.
c. and d. How many cdrs does last need without considering length? If the length is 1, it needs 0. If the length is 2, it needs 1. In general it needs (n-1) times cdr. We already know how often last calls length, so we can calculate the number of all calls. There are (n-1) calls from last directly. For each iteration in last we need 1 call of length. And each call of length needs (k+1) cdrs. If we merge everything together, we get the following table

len of list     cdr from last      calls of length     cdr from length
    1               0                    1                 1
    2               1                    2                 2 + 1
    3               2                    3                 3 + 2 + 1
    ...
    n              (n-1)                 n                 n + (n-1) + (n-2) + ... + 1

Now we just have to add cdr from last and cdr from length and get:
(n-1) + sum_{i=1}{n} i = (n-1) + frac{n(n-1)}{2} = frac{n^2 + 3n - 2}{2}
Which is Theta(n^2) in Theta notation.

Exercise 7.47: Write a procedure map-2 that takes a procedure and two lists as arguments and returns the list obtained by mapping the procedure over the two lists, drawing the two arguments from the two lists. Write this procedure map-2. You may assume that the lists have the same length.

Solution:

(define map-2
  (lambda (f lst1 lst2)
    (if (null? lst1)
      '()
       (cons (f (car lst1) (car lst2)) (map-2 f (cdr lst1) (cdr lst2))))))