CSC151 2007S, Class 53: Discussion of Exam 3

Admin:
* Exam 3 returned (for those who turned it in on time).
* This week: 
  * Discussion of Exam 3 (Today); 
  * What is CS, Revisited (Tomorrow); 
  * Wrapup (Wednesday).  Attendance on Wednesday is MANDATORY.  (More so
    than on normal days.)
    * If you miss, your attendance grade WILL drop.
  * Preparation for Final (Friday) (optional; food)
* I am working on a makeup assignment for those who are unhappy with 
  a homework grade.

Overview:
* General Observations.
* Specific Problems.

/General Observations/

* Still some problems with six P's.
* Hard exam, generally good job.
  * Almost no one screwed up multiple problems.

/Problem 4: Nth-Smallest/

Documentation

;;; Procedure:
;;;   nth-smallest
;;; Parameters:
;;;   n, an integer
;;;   lst, a list
;;;   precedes?, a binary predicate
;;; Purpose:
;;;   To give the nth smallest value in the list, as determined
;;;   by precedes?.
;;; Produces:
;;;   val, the nth smallest value
;;; Preconditions:
;;;   lst should be homogeneous
;;;   n is limited to the length of the list
;;;    that is, 0 <= n < (length lst)
;;;   precedes? should be applicable to any two elements of lst.
;;;   lst is not null (implicit in restrictions on length).
;;;   lst has no duplicate elements.
;;;   precedes? must be transitive.
;;; Postconditions:
;;;   There are n values smaller than val.  By 'x is smaller than val', 
;;;     we mean (precedes? x val)

;;; Issue: What if we want to allow duplicate elements?
;;; Postconditions:
;;;   val is equivalent to (list-ref (sort lst precedes?) n)
;;; Alternates abound:

Code online at Examples/nth-smallest.scm

/Problem 3: Sorting/

Expected form of all three problems (one of the following)

(sort lst (lambda (val1 val2) ...))

OR

(define comparator 
  (lambda (val1 val2)
     ...))
(sort lst comparator)

OR

(let ((comparator (lambda (val1 val2) ...)))
  (sort lst comparator))

a. By length of word
(sort words (lambda (word1 word2) (<= (string-length word1) (string-length word2))))

b. By average grade
(let ((average (lambda (lst) (/ (apply + lst) (length lst)))))
  (sort people (lambda (person1 person2)
                 (<= (average (cdr person1)) (average (cdr person2))))))
* Issue: Some people did total, rather than average

c. By point
(define print-first?
  (lambda (pt1 pt2)
    (or (< (cdr pt1) (cdr pt2))
        (and (= (cdr pt1) (cdr pt2))
             (or (and (even? (cdr pt1)) (<= (car pt1) (car pt2))
                 (and (odd? (cdr pt1)) (>= (car pt1) (car pt2)))))))))

Interesting (failed) strategy: Sort by x value and then sort again by y
value.

Problem 2: LOTS OF FUN with Higher-Order procedures

. [10 points] Write a procedure, (select-Bs lst), that, given a list of real numbers, selects only those that are at least 80 and strictly less than 90.

(define B? ...)
(define select-Bs 
  (lambda (lst)
    (select B? lst)))
(define select-Bs (l-s select B?))
(define B?
  (lambda (grade)
    (and (< grade 90) (<= 80 grade))))
(define B? (both (r-s < 90) (l-s <= 80)))

(define select-Bs (l-s select (both (r-s < 90) (l-s <= 80))))

b. [10 points] Write a procedure, (make-filter pred?), that returns a filter. The filter is a procedure of one parameter (a list, lst) which returns a new list by removing all the elements of the lst for which pred? holds. For example,

(define make-selector
  (lambda (pred?)
    (lambda (lst)
      (select pred? lst))))

(define make-selector
  (lambda (pred?)
    (l-s select pred?)))
(define make-selector
  (l-s l-s select))

(define make-filter
  ; Negate the predicate and then make a selector
  (lambda (pred?)
    (make-selector (negate pred?))))

(define o
  (lambda (f g)
    (lambda (x)
      (f (g x)))))

(define make-filter
  (o make-selector negate))

(define make-filter
  (o (l-s l-s select) negate))

c. [5 points] As you may recall, in an earlier assignment you wrote a procedure, (intersect lst1 lst2) in which lst1 and lst2 are lists of symbols (with no duplicates), representing sets. Now that you have the higher-order toolbox, you can write the solution much more concisely. Do so. You may assume that lst1 and lst2 are proper sets: That is, neither of the lists contains duplicate elements. 
(define intersect
  (lambda (lst1 lst2)
    (select "member of lst1" lst)
(define intersect
  (lambda (lst1 lst2)
    (select (r-s member? lst1) lst)