October 2011

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

Given two strings of lowercase letters, a and b, print the longest string x of lowercase letters such that there is a permutation of x that is a subsequence of a and there is a permutation of x that is a subsequence of b.

Problem: Sphere Online Judge (SPOJ) – Problem CPRMT

Solution: That’s short and nice problem. You have to find all letters which are in both strings. I’d actually like to see some other implementations of this. I bet there are some languages which handle this in a smart way.

def intersection(lst1, lst2):
    same = []
    if len(lst1) > len(lst2):
        for k in lst1:
            try: # checks if element k is in lst2
                lst2.remove(k)
                same.append(k)
            except:
                pass
    else:
        for k in lst2:
            try:
                lst1.remove(k)
                same.append(k)
            except:
                pass
    same.sort()
    return same


while True:
    try:
        inp1 = raw_input()
        inp2 = raw_input()

        common = intersection(list(inp1), list(inp2))
        print "".join(common)
    except:
        break

Concrete Abstractions: Chapter 8

#85/111: Machine Learning

SPOJ: 1728. Common Permutation

#84/111: R in a Nutshell