Exam 3: Sophisticated Scheming

Topics: Vectors, numeric recursion.

Document and write a procedure, (vector-rotate-1! vec) that rotates the elements in vec to the "left". That is, vector-rotate-1! puts the initial element of vec at the end, the element at position 1 in position 0, the element at position 2 in position 1, and so on. For example,

> (define vec1 (vector 'a 'b 'c 'd 'e))
> (define vec2 (list->vector (iota 8)))
> (vector-rotate-1! vec1)
> vec1
#(b c d e a)
> vec2
#(0 1 2 3 4 5 6 7)
> (vector-rotate-1! vec2)
> (vector-rotate-1! vec2)
> vec2
#(2 3 4 5 6 7 0 1)

Topics: Vectors, code reuse, higher-order procedures

Write, but do not document, a procedure, (vector-rotate! vec n) that rotates the elements in vec to the "left" by n places.

> (define vec1 (vector 'a 'b 'c 'd 'e))
> (vector-rotate! vec1 3)
> vec1
#(d e a b c)

Topics: Higher-order procedures, numeric recursion.

(image-variant picture
               (o rgb-darker rgb-darker rgb-darker rgb-darker rgb-darker))

> (define plus5 (nest (l-s + 1) 5))
> (plus5 6)
11
> (define list5 (nest list 5))
> (list5 6)
(((((6)))))
> (nest list 0)
n must be at least 1, given 0
> (define duplicate (lambda (val n) ((nest (l-s cons val) n) null)))
> (duplicate "hello" 5)
("hello" "hello" "hello" "hello" "hello")

Topics: Strings, higher-order procedures.

Document and implement the function (string-map proc str), which produces a new string in which proc has been applied to every character in the string str.

For example:

> (string-map char-upcase "Banana")
"BANANA"
> (string-map char-downcase "Banana")
"banana"
> (string-map (o integer->char increment char->integer) "Banana")
"Cbobob"
> (string-map (o integer->char increment char->integer) "Apple")
"Bqqmf"
> (string-map (o integer->char (l-s + 65) (l-s - 90) char->integer char-upcase) "Banana")
"YZMZMZ"

Hint for documentation: proc is a procedure. What are the types of its parameter and its value produced?

Topics: Strings, characters, higher-order procedures, conciseness.

Write, but do not document, a procedure (string-invert-case str) that transforms every upper-case letter in str into a lower-case letter, and vice versa. Make your definition as concise as possible.

For example:

> (string-invert-case "Banana")
"bANANA"
> (string-invert-case "Banana?!")
"bANANA?!"
> (string-invert-case "davisjan@cs.GRINNELL.edu")
"DAVISJAN@CS.grinnell.EDU"
> (string-invert-case "This Is Silly")
"tHIS iS sILLY"

Topics: Strings, characters, higher-order procedures, apply.

Inspired by: John Motil's BookNumber assignment

The International Book Standard Number (ISBN) is a special code used to identify books. An ISBN consists of nine digits followed by a tenth check character. This check character serves to detect errors if the ISBN is accidentally misread or mistyped.

Write a procedure, (isbn-check-character isbn), according to the following documentation.

;;; Procedure:
;;;   isbn-check-character
;;; Parameter:
;;;   isbn, a string
;;; Produces:
;;;   check-char, a character
;;; Purpose:
;;;   To compute the ISBN check character for isbn.
;;; Preconditions:
;;;   (string-length isbn) is 9.
;;;   isbn contains only characters representing digits, #\0 - #\9.
;;; Postconditions:
;;;   check-char is either #\X or a character representing 
;;;       a digit, #\0 through #\9.
;;;   check-char is computed via ISBN check algorithm below.
;;;
;;; Process:
;;;   The following algorithm is used to compute the check character.
;;;   1. Compute the sum of 1 times the first digit, two times the 
;;;      second digit, three times the third digit, and so on up to 
;;;      9 times the ninth digit.
;;;   2. Compute the remainder of this sum divided by 11.
;;;   3. If the remainder is 10, then the check character is #\X.
;;;      Otherwise, the check character is a digit, #\0 - #\9, 
;;;      representing the remainder.
;;;
;;; Practicum:
;;;   > (isbn-check-character "123456789")
;;;   #\X
;;;   > (isbn-check-character "020508005")
;;;   #\7

Hint 1: The digit #\0 corresponds to the integer 48. You can convert a string of digits into a list of equivalent numbers using (map (o (r-s - 48) char->integer) (string->list str)).

Hint 2: Break the problem down into smaller steps. Implement and test one step at a time.

Topics: Trees, predicates, verifying preconditions, reading documentation.

In the reading on trees, you learned how a tree can be flattened into a list structure with the following procedure.

;;; Procedure:
;;;   tree-flatten
;;; Parameters:
;;;   tree, a tree
;;; Purpose:
;;;   Convert a tree structure into a similar list structure.
;;; Produces:
;;;   lst, a list
;;; Preconditions:
;;;   none
;;; Postconditions:
;;;   lst is a simple list (that is, it contains no sublists).
;;;   Each value that appears in lst appears in tree.
;;;   Each value that appears in tree appears in lst.
;;;   If a precedes b in tree, then a precedes b in lst.
(define tree-flatten
  (lambda (tree)
    (if (pair? tree)
        (append (tree-flatten (car tree))
                (tree-flatten (cdr tree)))
        (list tree))))

As you saw in the reading on searching, it can be useful to determine whether a vector is sorted. Lists, like vectors, are simply an ordered collection of items. We could therefore ask whether the list containing a flattened tree is sorted as a means of asking whether a tree is sorted. This test of a "sorted tree" seems somewhat indirect, and its implementation strikes us as inefficient. Is there a better way to define and test for a sorted tree? As you might suppose, there is.

Let us consider the cases from tree-flatten. A leaf is necessarily sorted. What does it mean for a pair to represent a sorted tree? First, both the left and right subtrees would certainly need to be sorted. We must also verify that when placed against one another (as they are with append above), these two flattened subtrees represent a correct ordering. For that to be true, the last element of the left subtree, which represents the largest item in that subtree, must precede the first item in the right subtree.

Using this definition of a sorted tree, implement the following number-tree-sorted?.

Here are several examples using number-tree-sorted?.

> (define ntree1 (cons (cons 1 (cons 2 3)) 4))
> (define ntree2 (cons (cons 5 (cons 6 3)) 7))
> (tree-flatten ntree1)
(1 2 3 4)
> (number-tree-sorted? ntree1)
(1 . 4)
> (tree-flatten ntree2)
(5 6 3 7)
> (number-tree-sorted? ntree2)
#f
> (number-tree-sorted? 4)
(4 . 4)
> (number-tree-sorted? (cons 1 #\A))
number-tree-sorted?: #\A is not a number

Here are documentation and the beginning of the procedure definition to get you started.

;;; Procedure:
;;;   number-tree-sorted?
;;; Parameters:
;;;   ntree, a number tree [Unverified.]
;;; Purpose:
;;;   Determine whether a number tree is sorted
;;; Produces:
;;;   extremes, a pair of numbers or the value #f
;;; Preconditions:
;;;   [No additional.]
;;; Postconditions:
;;;   If ntree is a leaf, or
;;;   if ntree is a pair, its left and right subtrees are both sorted, 
;;;      and the largest value in the left subtree is no greater than  
;;;      the smallest value in the right subtree, 
;;;         then extremes is a pair whose car is the smallest value 
;;;            in ntree and whose cdr is the largest value
;;;            in ntree.
;;;   Otherwise, result is #f.
(define number-tree-sorted?
  (lambda (ntree)
    (if (pair? ntree)
      (let ((left-sorted (number-tree-sorted? (car ntree)))
            (right-sorted (number-tree-sorted? (cdr ntree))))
        ...

Hints: Note the return value provides useful information about subtrees in addition to whether or not they are sorted. As we suggest in the skeleton code above, use let to store the values produced by recursive calls to the predicate on the left and right subtrees, respectively. If the subtrees are not sorted, how will you know? What should you return? If the subtrees are sorted, what do these stored values tell you? How can you use that to determine whether the given tree is also sorted? Also: what value should be produced for a leaf?

Topics: Searching, list recursion.

The built-in version of assoc returns the first element of the association list whose car matches the key. Write, but do not document, an alternate version, (assoc-last key alist), that returns the last element of the association list whose car matches the key or returns #f if no match is found.

Topics: Analyzing procedures, searching, assoc.

Below we rename to my-assoc the implementation of assoc provided in an earlier reading:

(define my-assoc
  (lambda (key alist)
    (cond
      ; If there are no entries left in the association list,
      ; there are no entries with the given key.
      ((null? alist) 
       #f)
      ; If the key we're looking for is the key of the first
      ; entry, then use that entry.
      ((equal? key (car (car alist))) 
       (car alist))
      ; Otherwise, look in the rest of the association list.
      (else 
       (my-assoc key (cdr alist))))))

In this problem, you will use define$ and analyze to count the number of steps taken by this implementation, 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 my-assoc on an association list of length N. How many recursive calls to the procedure are required when the search is unsuccessful? Express the number of calls to my-assoc in terms of N.

(b) How many recursive calls to the procedure my-assoc are required on average to search a list of length 4 when the search is successful? That is, consider how many steps it takes to search for (and find) the first, second, third, and fourth items in the list, respectively; report the average of these four numbers.

(c) How many recursive calls to the procedure my-assoc are required on average to search a list of length 8 when the search is successful?

(d) How many recursive calls to the procedure my-assoc are required on average to search a list of length N when the search is successful? Express the number of calls to my-assoc in terms of N.

Topics: Unit testing, binary search.

At the beginning of the lab on binary search, you informally evaluated the correctness of a binary search procedure. In this problem, we ask you to test this procedure formally and systematically.

The following implementation of binary search has a subtle bug.

;;; Procedure:
;;;   binary-search
;;; Parameters:
;;;   vec, a vector to search
;;;   get-key, a procedure of one parameter that, given a data item,
;;;     returns the key of a data item
;;;   may-precede?, a binary predicate that tells us whether or not
;;;     one key may precede another
;;;   key, a key we're looking for
;;; Purpose:
;;;   Search vec for a value whose key matches key.
;;; Produces:
;;;   match, a number.
;;; Preconditions:
;;;   The vector is "sorted".  That is,
;;;     (may-precede? (get-key (vector-ref vec i))
;;;                   (get-key (vector-ref vec (+ i 1))))
;;;     holds for all reasonable i.
;;;   The get-key procedure can be applied to all values in the vector.
;;;   The may-precede? procedure can be applied to all pairs of keys
;;;     in the vector (and to the supplied key).
;;;   The may-precede? procedure is transitive.  That is, if
;;;     (may-precede? a b) and (may-precede? b c) then it must
;;;     be that (may-precede? a c).
;;;   If two values are equal, then each may precede the other.
;;;   Similarly, if two values may each precede the other, then
;;;     the two values are equal.
;;; Postconditions:
;;;   If vector contains no element whose key matches key, match is -1.
;;;   If vec contains an element whose key equals key, match is the
;;;     index of one such value.  That is, key is 
;;;       (get-key (vector-ref vec match))
(define binary-search
  (lambda (vec get-key may-precede? key)
    ; Search a portion of the vector from lower-bound to upper-bound
    (let search-portion ((lower-bound 0)
                         (upper-bound (- (vector-length vec) 1)))
      (if (>= lower-bound upper-bound)
          ; Did we find it?
          (if (equal? key (get-key (vector-ref vec lower-bound)))
              lower-bound ; Yes!
              -1) ; No!
          ; Keep searching
          (let ((midpoint (+ lower-bound (quotient (- upper-bound lower-bound) 2))))
            (if (may-precede? key (get-key (vector-ref vec midpoint)))
                (search-portion lower-bound (- midpoint 1))
                (search-portion (+ midpoint 1) upper-bound)))))))

Write a test suite, using the MediaScheme unit testing tools, to test for errors in an implementation of binary search. Your tests should all pass for the correct version of binary search from the lab; some should fail for the buggy version of binary search given above. Comment your tests to explain the purpose of each one.

Hints: In your test suite, you should test that a correct result is given

In addition to writing tests, you will need to create vectors that will be searched in your tests. You will need to create at least two different vectors and write at least ten test cases in order to cover all possible combinations of conditions.

Here is a vector and two tests to start you off:

(define test-vector
  (vector (cons 2 "two")
          (cons 4 "four")
          (cons 6 "six")
          (cons 8 "eight")
          (cons 10 "ten")))

; Search for key in position 0
(test! (binary-search test-vector car <= 2) 0)
; Search for non-existent key that would appear before position 0
(test! (binary-search test-vector car <= 1) -1)