Quiz #1

Problem 1

(define (constructor a b)
  (define fn (lambda (param)
               (cond ((equal? param 'first) a)
                     ((equal? param 'second) b)
                     ((equal? param 'type) 'pair) ) ))
  fn)

a) What type of data abstraction is this constructor related to? Explicit dispatch, data-directed, message passing, or none at all?

b) What Scheme data type shares similar data storage characteristics to this data construct.

c) Write selectors for the data created by this constructor. Make the names parallel the Scheme data type's selectors. For example mp-??? where ??? is replaced with the name of the Scheme selector.

Problem 2

Constructors:

(make-btree datum left right) returns a btree

Selectors:

(get-datum btree) returns a datum

(get-left btree) returns a btree

(get-right btree) returns a btree

(get-children btree) returns a list of non-empty btrees

Predicates:

(empty-btree? btree) retunrs a boolean

Constants:

empty-btree is a btree

a) Define a procedure "reorder" that takes a btree as its parameter and returns a btree with the datum of the root and its immediate children in a pattern where the root has the larger of the numbers.

     5          5    |      3          5    |      2          5
    / \        / \   |     / \        / \   |     / \        / \
   3   2  =>  3   2  |    5   2  =>  3   2  |    3   5  =>  3   2
  / \        / \     |   / \        / \     |   / \        / \
 4   1      4   1    |  4   1      4   1    |  4   1      4   1

b) Define a procedure "tree-height" that takes a btree as its parameter and returns the height of the tree (the total number of levels).

     5
    / \
   3   2  =>  3 
  / \
 4   1

c) Define a procedure "reorder-pass" that performs a single pass of moving the nodes of the tree into a numberically descending order. (Hint: This will need to be a post-order recursive traversal).

     5          6          6    |      5          8          8
    / \        / \        / \   |     / \        / \        / \
   3   2  =>  5   2  =>  5   2  |    3   2  =>  5   2  =>  7   2
  / \        / \        / \     |   / \        / \        / \
 4   6      4   3      4   3    |  7   8      7   3      5   3
                                |
 Original   1st Pass   2nd Pass |  Original   1st Pass   2nd Pass

d) Define a procedure "full-reorder" that performs n single reorder-passes where n is the height of the tree. This is enough passes to put all of the elements in descending order.

Problem 3

Draw Box & Pointer Diagrams that result from evaluating the following:

a) (cons 'a (cdr (car (list '(1 2) 3 4))))

b) (cons '(cons 4 5) (list 7 8))

What does Scheme print for each result of evaluating the two expressions?