Thank you to the students who showed up so that we'll have notes that that other students can read over later.

Finding This Page

• Go to http://www.cs.grinnell.edu/~rebelsky/
• Click on "CSC 151" at the top of the page
• Click on "EBoard" in the "Current" row

Overview

• About the quiz.
• Your questions.
• Sample quiz questions.
• More of your questions.

The Quiz

Topics

• Association lists (linear search)
• Binary search
• Sorting (conceptually)

Types of questions

• What does this code do?
  • Give the output
  • Document
  • Insert (display ...), what will be displayed?
• Write code to do the following ...
  • From scratch
  • With a template

Questions

[None]

Sample Quiz Questions

(define named-colors
  (list (list "black"         0   0   0  "bw" "web-safe")
        (list "blah grey"   153 153 153  "bw" "web-safe")
        (list "green"         0 255   0  "primary" "rainbow")
        (list "blueish"      10  10 255  "blues")
        (list "green"         0 128   0  "primary" "rainbow")
        (list "indigo"      102   0 255  "rainbow" "web-safe")
        (list "medium grey" 128 128 128  "bw")
        (list "blood red"   102   0   0  "reds" "web-safe")
        (list "white"       255 255 255  "bw" "web-safe")
        (list "blue"          0   0 255  "primary" "rainbow" "web-safe")
        (list "orange"      255 119   0  "rainbow")
        (list "off white"   250 250 250  "bw")
        (list "pale red"    255 240 240  "reds")
        (list "red"         255   0   0  "primary" "rainbow" "web-safe" "reds")
        (list "violet red"  204  50 153  "reds")
        (list "violet"       79  47  79  "rainbow")
        (list "yellow"      255 255   0  "rainbow" "secondary" "web-safe")))

Simple output

What is the output for (assoc "green" named-colors)?

What is the output for (assoc "rainbow" named-colors)?

What is the output for (assoc "violet" named-colors)?

Solutions

What is the output for (assoc "green" named-colors)?

Since assoc finds the first match, it's

    '("green"         0 255   0  "primary" "rainbow")

What is the output for (assoc "rainbow" named-colors)?

"rainbow" is not the car of any list, so we get #f.

What is the output for (assoc "violet" named-colors)?

We need exact matches, so we get the "violet" not the "violet red".

    '("violet"       79  47  79  "rainbow")

Write code

Write instructions to generate the IRGB color for "violet red", assuming we have to find the components in the list of named colors.

Write a program

Write a program that finds the first web-safe color.

A Solution

(define first-web-safe
  (lambda (colors)
    (cond
      [(null? colors)
       #f]
      [(member "web-safe" (cddddr (car colors)))
       (car (car colors))]
      [else
       (first-web-safe (cdr colors))])))

A more general solution w/o member

(define first-in-category
  (lambda (colors category)
    (cond
      [(null? colors)
       #f]
      [(any (section equal? category <>) (cddddr (car colors)))
       (car (car colors))]
      [else
       (first-in-category (cdr colors) category)])))

Write a program

Finish the following program that finds all the web-safe colors.

(define find-web-safe
  (lambda (colors)
    (cond
      [(null? colors)
       __________]
      [_________________
       (cons (car colors) (find-web-safe (cdr colors)))]
      [else
       __________________])))

More data

(define objects-by-name
  (vector
   (list "Amy"       "ellipse"   "blue"    90  50 25  5) ;  0
   (list "Bob"       "ellipse"   "indigo"  80  40 35 30) ;  1
   (list "Charlotte" "rectangle" "blue"     0  40  5 45) ;  2
   (list "Danielle"  "rectangle" "red"      0 140 35 15) ;  3
   (list "Devon"     "rectangle" "yellow"  80   0 10  5) ;  4
   (list "Erin"      "ellipse"   "orange"  60  50 10 15) ;  5
   (list "Fred"      "ellipse"   "black"    0 110 30 30) ;  6
   (list "Greg"      "ellipse"   "orange" 110  10 35 50) ;  7
   (list "Heather"   "rectangle" "white"  100 140 35 50) ;  8
   (list "Ira"       "ellipse"   "red"    100 100  5 50) ;  9
   (list "Janet"     "ellipse"   "black"   60  70  5 20) ; 10
   (list "Karla"     "ellipse"   "yellow"  20 110 25 10) ; 11
   (list "Leo"       "rectangle" "yellow"  60  40 30 50) ; 12
   (list "Maria"     "ellipse"   "blue"    30  10  5 50) ; 13
   (list "Ned"       "rectangle" "yellow"   0  50 45 15) ; 14
   (list "Otto"      "rectangle" "red"    100  40 10 20) ; 15
   (list "Otto"      "rectangle" "red"    101  40 10 20) ; 16
   (list "Otto"      "rectangle" "red"    102  40 10 20) ; 17
   (list "Paula"     "ellipse"   "orange" 100  20 50 25) ; 18
   (list "Quentin"   "ellipse"   "black"   40 130 35 50) ; 19
   (list "Rebecca"   "rectangle" "green"  110  70 25 35) ; 20
   (list "Sam"       "ellipse"   "white"   20 120 35 40) ; 21
   (list "Sam"       "ellipse"   "white"   21 120 35 40) ; 22
   (list "Ted"       "rectangle" "black"   20   0 10 20) ; 23
   (list "Urkle"     "rectangle" "indigo"  40 110 10  5) ; 24
   (list "Violet"    "rectangle" "violet"  80  80 50 20) ; 25
   (list "Xerxes"    "rectangle" "blue"    60 130 25 35) ; 26
   (list "Yvonne"    "ellipse"   "white"   40 110 50 40) ; 27
   (list "Zed"       "rectangle" "grey"    90 60  25  5) ; 28
  ))

Show steps

Suppose we inserted the line (display (list 'kernel lower-bound upper-bound)) at the top of the kernel for binary search. What values would we see as we searched for "Sam"?

Compute results

What is (binary-search objects-by-name car string-ci<=? "Xerxes")?

Write expressions

The form of binary search is (binary-search sorted-vector get-key may-precede? key). Given some sorted vector, write an expression to find _ in that vector.

Notes on solution

Your get-key will usually be car or cadr or something similar.

Your may-precede? will usually be <= or string-ci<=?.

Sorting: Preconditions

Consider a procedure, (sort lst may-precede?). What preconditions do you expect that procedure to have?

A Solution

Can we write (sort (list 1 2 3) string-ci<=?)? No! string-ci<=? applies to strings and 1, 2, and 3 are not strings.

Can we write (sort (list 1 2 3) (lambda (x y) (zero? (random 2))))

;;; Preconditions:
;;;   may-precede? is applicable to any two elements in lst.
;;;   may-precede? is sensible - it gives a "total order" to elements

Sorting: Postconditions

Consider a procedure, (sort lst may-precede?). What postconditions do you expect that procedure to have?

;;; Postconditions:
;;;   result is sorted
;;;     For any two neighboring elements, x and y, (may-precede? x y)

If you think that's enough, here's a sorting routine

    (define sort
      (lambda (lst may-precede?)
        null))

We need to say something about the elements. We could try "result has the same number of elements as lst"

    (define sort
      (lambda (lst may-precede?)
        (if (null? lst)
            null
            (make-list (length lst) (car lst)))))

Preferred postcondition

;;; result is a permutation of lst.