Exam 3: Sophisticated Scheming

Topics: Vectors, verifying preconditions, higher-order procedures

Write a procedure (vector-ref-mutate! vec index proc) that applies proc to the item in vec at index, storing the result in the same location.

The procedure vector-ref-mutate! should verify its preconditions. However, you need not verify any properties of proc other than its type.

> (define numbers (make-vector 4 0))
> (vector-ref-mutate! numbers 2 increment)
> numbers
#(0 0 1 0)
> (vector-ref-mutate! numbers 3 (l-s + 5))
> numbers
#(0 0 1 5)
> (vector-ref-mutate! numbers 4 decrement)
vector-ref-mutate!: index 4 out of bounds for vector #(0 0 1 5)
> (vector-ref-mutate! numbers 0 5)
vector-ref-mutate!: expected procedure for 3rd parameter; given 5

Topics: Vectors, numeric recursion, randomness

The lab on randomized drawing used the following two procedures to simulate rolling a pair of dice.

;;; Procedure:
;;;   roll-a-die
;;; Parameters:
;;;   None
;;; Purpose:
;;;   To simulate the rolling of one six-sided die.
;;; Produces:
;;;   An integer between 1 and 6, inclusive.
;;; Preconditions:
;;;   [None]
;;; Postconditions:
;;;   Returns an integer between 1 and 6, inclusive.
;;;   It should be difficult (or impossible) to predict which
;;;     number is produced.
(define roll-a-die
  (lambda ()
    (+
      (random 6)    ; a value in the range [0 .. 5]
      1)))          ; now in the range [1 .. 6]

;;; Procedure:
;;;   pair-a-dice
;;; Parameters:
;;;   [None]
;;; Purpose:
;;;   Roll two six-sided dice and find their sum.
;;; Produces:
;;;   roll, an integer
;;; Preconditions:
;;;   [No additional]
;;; Postconditions:
;;;   2 <= roll <= 12
;;;   Across multiple calls, the various rolls have the same probabilities 
;;;     as we would get from rolling two dice.
(define pair-a-dice
  (lambda ()
    (+ (roll-a-die) (roll-a-die))))

Computational scientists often find it difficult to analyze quantities mathematically and resort to simulation to get an approximate answer.

Write, but do not document, a procedure (count-rolls n) that rolls a pair of six-sided dice n times. It should produce a vector of length 13, where the value at each index is the number of times that total (the index) came up.

Hints: Indices 0 and 1 will always contain zero, since it is not possible to roll two dice and produce a zero or a one. You should use the procedures pair-a-dice and vector-ref-mutate! in your solution.

> (count-rolls 1)
#(0 0 0 0 0 0 0 0 0 0 1 0 0)
> (count-rolls 100)
#(0 0 2 6 15 12 10 15 12 12 11 4 1)

Write and document a procedure (char-shifter amount), which produces a procedure that takes a character and shifts it by amount, ignoring any wrap-around.

You should strive to make your procedure as concise as possible.

> (define char-encode-1 (char-shifter 5))
> (char-encode-1 #\H)
#\M

Of course, Caesar ciphers are much more interesting when applied to strings, rather than to individual characters. It is also natural to think of a cipher as a function from strings to strings, rather than from numbers to strings. Hence, we'd like a procedure that builds ciphers.

Write, but do not document, a procedure (shift-encoder amount) that returns a procedure that takes a string as input and produces a string where each character is replaced by another whose collating sequence number differs from the original by amount.

You should strive to make your procedure as concise as possible.

> (define encode-1 (shift-encoder 5))
> (encode-1 "HELLO")
"MJQQT"
> (define encode-2 (shift-encoder 2))
> (encode-2 "MJQQT")
"OLSSV"
> (define decode-12 (shift-encoder -7))
> (decode-12 "OLSSV")
"HELLO"
> ((o decode-12 encode-2 encode-1) "WORLD")
"WORLD"

Consider the following implementation of assoc:

(define assoc
  (lambda (key dict)
    (letrec ((kernel
              (lambda (remaining)
                (cond ((null? remaining) null)
                      ((= key (caar remaining)) (car remaining))
                      (else (kernel (cdr remaining))))))
             (all-pairs? 
               (lambda (lst)
                 (or (null? lst) 
                     (and (pair? (car lst)) (all-pairs? (cdr lst)))))))
      (if (or (not (list? dict)) (not (all-pairs? dict)))
          (error "assoc: expected a list of key-value pairs; given" dict)
          (kernel (cdr dict))))))

We have manually tested this procedure using the following input, and it appears to work correctly:

> (assoc 3 (list (cons 1 2) (cons 3 4) (cons 5 6)))
(3 . 4)
> (assoc 1 (list 1 2 3))
assoc: expected a list of key-value pairs; given (1 2 3)

However, our implementation has several bugs. Using begin-tests!, end-tests!, test!, and test-error!, write a test suite for the assoc procedure. Consult the reading on association lists for a refresher on the correct behavior of assoc.

Note: You should include a comment with each test indicating its purpose. For example:

; Known equilateral triangle
(test! (classify-triangle 1 1 1) "equilateral") 

; Impossible triangle: hypotenuse exceeds sum of other two sides
(test-error! (classify-triangle 1 1 3)) 

Hint: Your test suite should include at least three tests that pass for the built-in assoc procedure and fail for our buggy procedure.

Note: This problem was revised on Tue, Nov 30.

Recall that merge sort is a divide-and-conquer algorithm: We make the sorting problem smaller by dividing the list into two halves, which are then sorted.

In the reading on merge sort, you were given the following implementation of a split procedure:

;;; Procedure:
;;;   split
;;; Parameters:
;;;   lst, a list
;;; Purpose:
;;;   Split a list into two nearly-equal halves.
;;; Produces:
;;;   halves, a list of two lists
;;; Preconditions:
;;;   lst is a list.
;;; Postconditions:
;;;   halves is a list of length two.
;;;   Each element of halves is a list (which we'll refer to as
;;;     firsthalf and secondhalf).
;;;   lst is a permutation of (append firsthalf secondhalf).
;;;   The lengths of firsthalf and secondhalf differ by at most 1.
;;;   Does not modify lst.
;;;   Either firsthalf or secondhalf may share cons cells with lst.
(define split
  (lambda (lst)
    ;;; kernel
    ;;;   Remove the first count elements of a list.  Return the
    ;;;   pair consisting of the removed elements (in order) and
    ;;;   the remaining elements.
    (let kernel ((remaining lst) ; Elements remaining to be used
                 (removed null)  ; Accumulated initial elements 
                 (count          ; How many elements left to use
                  (quotient (length lst) 2)))
      ; If no elements remain to be used,
      (if (= count 0)
          ; The first half is in removed and the second half
          ; consists of any remaining elements.
          (list (reverse removed) remaining)
          ; Otherwise, use up one more element.
          (kernel (cdr remaining)
                  (cons (car remaining) removed)
                  (- count 1))))))

Consider the following alternative, split-v2:

(define split-v2
  (lambda (lst)
    (let kernel ((rest lst)
                 (left null)
                 (right null))
      (if (null? rest)
          (list left right)
          (kernel (cdr rest) (cons (car rest) right) left)))))

In this problem, you will use define$ and analyze to count the number of steps taken by each version of split, and then you will interpret the results. Recall that computer scientists analyze how many steps it takes to run an algorithm based on the size of its parameters. That is, if an algorithm is given a list of length N, we might want to know that that algorithm takes 4N+3, or N(N-1)/2, or log2(N) steps.

(a) Consider calling the procedure split on a list of length N. How many calls to the kernel procedure are required? Express the number of calls to kernel in terms of N.

(b) Consider calling the procedure split-v2 on a list of length N. How many calls to the kernel procedure are required? Express the number of calls to kernel in terms of N.

Now consider using split or split-v2 in the context of the merge-sort procedure from the reading on merge sort.

(c) Again using define$ and analyze, compare how split and split-v2 perform in the context of the merge-sort function.

Note: After you complete the rest of the exam, you may wish to attempt the OPTIONAL parts for bonus points, below.

(d) (OPTIONAL) Consider calling (merge-sort (random-numbers N) <=). Express the number of calls to split's kernel procedure in terms of N.

(e) (OPTIONAL) Modify the code for merge-sort so that it uses the split-v2 function instead of split. Consider calling (merge-sort (random-numbers N) <=). Express the number of calls to split-v2's kernel procedure in terms of N.

Recall from the the reading on trees that the depth of a tree can be defined as the greatest number of hops (or links) from the root to a leaf. One might also be interested in the shortest number of hops from the root to a leaf. Write, but do not document, a procedure (tree-min-depth tree) that calculates the distance to the shallowest leaf of its argument.

> (tree-min-depth (cons 'a 'b))
1
> (tree-min-depth (cons 'a (cons 'b 'c)))
1
> (tree-min-depth (cons (cons 'a 'b) (cons 'c 'd)))
2
> (tree-min-depth (cons (cons 'a 'b) (cons (cons 'c 'd) 'e)))
2
> (tree-min-depth 'a)
0

A "balanced" tree is one which has no subtrees (i.e., it is simply a leaf) or whose two subtrees have the same height and are themselves both balanced.

The following version of a predicate tree-balanced? is correct, but extremely inefficient because it involves multiple traversals of the tree. At each pair, one traversal is done with the tree-depth procedure, and this is followed by a traversal done with recursive calls to tree-balanced?.

(define tree-balanced?
 (lambda (tree)
   (or (not (pair? tree))
       (let ((left-height (tree-depth (car tree)))
             (right-height (tree-depth (cdr tree))))
         (and (= left-height right-height)
              (tree-balanced? (car tree))
              (tree-balanced? (cdr tree)))))))

Write and document a more efficient tree-balanced? procedure that traverses the tree only once by returning the tree's height when the tree is balanced and #f otherwise.

> (tree-balanced? (cons 'a 'b))
1
> (tree-balanced? (cons 'a (cons 'b 'c)))
#f
> (tree-balanced? (cons (cons 'a 'b) (cons 'c 'd)))
2
> (tree-balanced? (cons (cons 'a 'b) (cons (cons 'c 'd) 'e)))
#f
> (tree-balanced? 'a)
0

Write, but do not document, a procedure (matrix-row-sum matrix) that returns a list containing the totals of all the numbers in each row of matrix, a list of lists as described above.

> (matrix-row-sum mtx-example)
(10 7 23)

Note: You should NOT implement this procedure using recursion.

Write, but do not document, a procedure (matrix-col-sum matrix) that returns a list containing the totals of all the numbers in each column of matrix, a list of lists as described above.

> (matrix-col-sum mtx-example)
(9 11 13 7)

Note: You should NOT implement this procedure using recursion. In addition to map and apply, you will find it helpful to use cons.