Sample Set of Learning Assessments (SoLA 2)

These are sample individual learning assessments of the approximate type and difficulty that you will encounter. They represent the LAs for the second Set of Learning Assessments.

Use section and composition to simplify computations.

Consider the following procedures

;;; (vowel? char) -> boolean
;;;   char : char?
;;; Determine if char is a vowel.
(define vowel?
  (let ([vowels (string->list "aeiou")])
    (lambda (ch)
      (integer? (index-of vowels (char-downcase ch))))))

;;; (count-vowels str) -> integer?
;;;   str : string?
;;; Count the number of vowels in str
(define count-vowels
  (lambda (str)
    (tally vowel? (string->list str))))

;;; (select-special-words words) -> list-of string?
;;;   words : list-of string?
;;; Selects all the special words in words using the ALTV criterion.
(define select-special-words
  (lambda (words)
    (filter (o (section > <> 2) count-vowels) words)))

a. What kinds of words does select-special-words select?

b. Explain how (o (section > <> 2) count-vowels) works as a predicate for such words.

c. Rewrite vowel? using section and composition but no lambda.

Refactor redundancy and add clarity in computations with let-bindings.

Consider the following procedure that contains some repetitious code.

;;; (letter->number ch) -> either integer? boolean?
;;;   ch : char?
;;; Converts ch to the corresponding number in the English alphabet.
;;; (1 for #\a or #\A, 2 for #\b or #\B, etc.).  Returns false (#f)
;;; if ch is not a letter in the English alphabet.
(define letter->number
  (lambda (ch)
    (cond
      [(<= (char->integer #\a) (char->integer ch) (char->integer #\z))
       (+ 1 (- (char->integer ch) 97))]
      [(<= (char->integer #\a) (+ (char->integer ch) 32) (char->integer #\z))
       (+ 1 (- (+ (char->integer ch) 32) 97))]
      [else #f])))

(check-equal? (map letter->number (string->list "abcde"))
              '(1 2 3 4 5)
              "First five lowercase letters")
(check-equal? (map letter->number (string->list "ABCDE"))
              '(1 2 3 4 5)
              "First five uppercase letters")
(check-equal? (map letter->number (string->list "XYZ"))
              '(24 25 26)
              "Last three uppercase letters")
(check-equal? (map letter->number (string->list "xyz"))
              '(24 25 26)
              "Last three lowercase letters")
(check-equal? (letter->number #\.)
              #f
              "Not a letter")

As you know, we should avoid redundant computations and magic numbers. Using local bindings (let or let*), remove the redundant computations and magic numbers from letter->number. You need not change the primary stucture of the cond, but you should not compute the same value twice.

Note: In case you didn’t know, 32 is the result of subtracting the collating sequence number of #\A from the collating sequence number of #\a. By adding 32, we switch from uppercase to lowercase. And 37 seems to be the collating sequence number of #a, but we probably shouldn’t count on that.

Document programs according to good software engineering principles.

Consider the following matching-indices procedure that finds the indices of elements of a list that match a particular predicate. (You need not understand all of the code, just what it does.)

(define matching-indices
  (lambda (pred? lst)
    (matching-indices-helper pred? lst 0)))

(define matching-indices-helper
  (lambda (pred? lst pos)
    (cond
      [(null? lst)
       null]
      [(pred? (car lst))
       (cons pos (matching-indices-helper pred? (cdr lst) (+ pos 1)))]
      [else
       (matching-indices-helper pred? (cdr lst) (+ pos 1))])))

> (define starts-with-a?
    (lambda (str)
      (char=? #\a (string-ref str 0))))
> (define words (list "and" "as" "the" "animals" "rode" "off" "into" "the" "sunset"
                      "after" "aiding" "the" "enchantress"))
> (matching-indices starts-with-a? words)
'(0 1 3 9 10)
> (list-ref words 3)
"animals"

a. Write the standard documentation for matching-indices.

b. Other than the broad types of pred? and lst, what restrictions does matching-indices impose on its parameters? For example, can you call (matching-indices odd? words)? Can you call (matching-indices (section substring <> 0 1) words)? Should you?

c. Suppose an integer, i, appears in the list of values returned by matching-indices. What an we guarantee about i (other than that it is a non-negative integer)?

Test programs according to good software engineering principles.

Consider the following not-yet-implemented procedure.

;;; (median numbers) -> real?
;;;   numbers : list-of real?
;;; Find the median of a list of a nonempty list of numbers using
;;; the standard approach.
(define median
  (lambda (numbers)
    (car numbers))) ; Incorrect, but a good placeholder.

Write a set of tests for median using check-= and/or check-equals?. Make sure to include at least three “expected” cases and at least three “edge” cases.

Here are some examples to get you started.

(check-= (median '(1 2 3))
         2
         0
         "An easy list of integers")
(check-= (median '(1.0 2 3 4))
         2.5
         0.00000001
         "A list of real numbers of even length.")

Use systematic debugging techniques to discover problems in code.

Suppose you find that a procedure that you have written is producing output other than you expect.

a. Which of the following are important steps you should commonly take to identify the error? (“Ask for help” is another one.)

• Write additional test cases to get a better idea of the scope of the error.

• Trace the code by hand to see if you get the same output.

• Throw away the procedure and start from scratch.

• Write additional test cases for your helper functions.

• Rename variables.

• Execute portions of the code (perhaps substituting in values for variables) in the interactions pane.

• Rearrange the right parentheses because you may have gotten them wrong.

• Get DrRacket to reindent the program to see if the structure it sees is the same as the structure you expect.

• Write down the algorithm in English and then check that the Racket code matches what you were planning.

• Defenestrate your computer.

• Look for places to break your procedure down into subprocedures so that you can test those subsolutions separately.

b. List one or two other approaches you might take.

Note: In the SoLA, I will likely ask you to apply one or more of these techniques.

Read and interpret programs involving recursive behavior over lists and/or numbers.

Consider the following recursive helper function written in Racket:

(define sl-helper
  (lambda (l a b)
    (if (null? l)
        (list (reverse a) (reverse b))
        (sl-helper (cdr l)
                   b
                   (cons (car l) a)))))

Here’s the primary function that calls it.

(define sl
  (lambda (l)
    (sl-helper l null null)))

Trace the call (sl '(p q r s t u))

When writing out your trace, you may step from a recursive call directly to the branch of the conditional the call evaluates to. You may also evaluate all pending sub-expressions in this resulting expression to values up until the next recursive call. For example, here is the start of the derivation to get you started:

    (sl (p q r s t u))
--> (sl-helper '(p q r s t u) '() '())
--> (sl-helper '(q r s t u) '() '(p))

Design and write recursive functions over lists.

Write a recursive procedure, (increasing-length? words), that takes a list of strings as input and ensures that every string is at least as long as the previous string. If so, it returns true. If not, it returns false.

Here’s a partial test suite.

(check-equal? (increasing-length '()) 
              #t
              "No strings: They are in increasing length")
(check-equal? (increasing-length? '("hello"))
              #t
              "A singleton")
(check-equal? (increasing-length? '("a" "b" "cd" "efg" "hij" "klmn"))
              #t
              "Some duplicate-length words")
(check-equal? (increasing-length? '("a" "bb" "ccc" "dddd" "eee"))
              #f
              "Okay until the end.")