CSC151.02 2016S, Review Session 13 (2016-05-05)
===============================================
**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
* 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.